Day 28: Conquering Three Questions — My 100-Day Journey

Introduction

Hey, fellow coders! 👋 Today marks twenty eighth day of my 100-day coding challenge. In this post, I’ll share my journey of conquering two + one Leetcode daily coding challenges. Let’s dive in!

Day 28

Coding Challenges

Challenge 1: Determine if String Halves Are Alike

Determine if String Halves Are Alike (Leetcode)

Solution 1

It was today’s Leetcode daily problem which involved simple implementation using set. This can also be achieved by using map.

bool halvesAreAlike(string s) {
  set<char> st({'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'});
  int count = 0;
  for (int i = 0; i < (s.size() / 2); i++) {
    if (st.find(s[i]) != st.end()) count++;
  }
  for (int i = s.size() / 2; i < s.size(); i++) {
    if (st.find(s[i]) != st.end()) count--;
  }
  return count == 0;
}

Challenge 2: Unique Paths II

Unique Paths II (Leetcode)

Solution 2

Recursive

int sol(vector<vector<int>>& g, int i, int j) {
  if (i >= g.size() || j >= g[i].size()) return 0;
  if (g[i][j] == 1) return 0;
  if (i == g.size() - 1 && j == g[i].size() - 1) return 1;
  return sol(g, i + 1, j) + sol(g, i, j + 1);
}
int uniquePathsWithObstacles(vector<vector<int>>& g) { return sol(g, 0, 0); }

Top down

int sol(vector<vector<int>>& g, int i, int j, vector<vector<int>> &dp) {
  if (i >= g.size() || j >= g[i].size()) return 0;
  if (dp[i][j] == -1) {
    if (g[i][j] == 1)
      dp[i][j] = 0;
    else
      dp[i][j] = sol(g, i + 1, j, dp) + sol(g, i, j + 1, dp);
  }
  return dp[i][j];
}
int uniquePathsWithObstacles(vector<vector<int>>& g) {
  vector<vector<int>> dp(g.size(), vector<int>(g[0].size(), -1));
  dp[g.size() - 1][g[0].size() - 1] = 1;
  if (g[g.size() - 1][g[0].size() - 1] == 1) return 0;
  return sol(g, 0, 0, dp);
}

Bottom Up (Memory Optimized)

int uniquePathsWithObstacles(vector<vector<int>>& g) {
  if (g[g.size() - 1][g[0].size() - 1] == 1) return 0;
  vector<unsigned int> dp(g[0].size() + 1, 0);
  dp[g[0].size() - 1] = 1;
  for (int i = g.size() - 1; i >= 0; i--) {
    for (int j = g[i].size() - 1; j >= 0; j--) {
      if (g[i][j] == 1)
        dp[j] = 0;
      else
        dp[j] = dp[j] + dp[j + 1];
    }
  }
  return dp[0];
}

Challenge 3: Longest Common Subsequence

Longest Common Subsequence (Leetcode)

Solution 3

Recursive

int sol(string t1, string t2, int i, int j) {
  if (i == t1.size() || j == t2.size()) return 0;
  if (t1[i] == t2[j]) {
    return 1 + sol(t1, t2, i + 1, j + 1);
  } else {
    return max(sol(t1, t2, i + 1, j), sol(t1, t2, i, j + 1));
  }
}
int longestCommonSubsequence(string text1, string text2) {
  return sol(text1, text2, 0, 0);
}

Top down

int sol(string t1, string t2, int i, int j, vector<vector<int>> &dp) {
  if (i == t1.size() || j == t2.size()) return 0;
  if (dp[i][j] == -1) {
    if (t1[i] == t2[j])
      dp[i][j] = 1 + sol(t1, t2, i + 1, j + 1, dp);
    else
      dp[i][j] = max(sol(t1, t2, i + 1, j, dp), sol(t1, t2, i, j + 1, dp));
  }
  return dp[i][j];
}
int longestCommonSubsequence(string text1, string text2) {
  vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));
  return sol(text1, text2, 0, 0, dp);
}

Bottom Up

int longestCommonSubsequence(string t1, string t2) {
  vector<vector<int>> dp(t1.size() + 1, vector<int>(t2.size() + 1, 0));
  for (int i = t1.size() - 1; i >= 0; i--) {
    for (int j = t2.size() - 1; j >= 0; j--) {
      if (t1[i] == t2[j])
        dp[i][j] = 1 + dp[i + 1][j + 1];
      else
        dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
  return dp[0][0];
}

Reflection

Embrace the journey of today with gratitude, for every moment is an opportunity to make a positive impact.

Conclusion

Thanks for joining me on this coding adventure. Feel free to share your thoughts and insights in the comments. Happy coding 🚀

Current Progress