LeetCode June Challenge - Day 9

Problem: LeetCode June Challenge - Day 9

Ideas:

  1. Another standard DP problem.
    • Base cases:
      • If s is empty, then it is always a substring of t.
      • If t is empty but s isn’t, then it isn’t a substring.
    • Recursion: given a prefix T of t and a prefix S of s, there are two possibilities:
      • Skip the last character of T.
      • If their last character is equal, we only need to check if after removing the last character, S is a substring of T.

Solution:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.length(), n = t.length();
        if(n < m) return false;

        bool dp[m+1][n+1];
        for(int i=0; i<=n; ++i) dp[0][i] = true;
        for(int i=1; i<=m; ++i) dp[i][0] = false;

        for(int j=1; j<=n; ++j)
            for(int i=1; i<=m; ++i){
                dp[i][j] = dp[i][j-1] ||
                           (s[i-1]==t[j-1] && dp[i-1][j-1]);
            }
        return dp[m][n];
    }
};