Leetcode 392 - Is Subsequence

題目

Problem#

給兩個字串 s 和 t 問 s 是不是 t 的子序列(Subsequence)

• 0 <= s.length <= 100
• 0 <= t.length <= 104

Follow-up: 當 s.length >= 10^9 時要怎麼做

想法#

當下想到 DP 的作法，看 s 和 t 的 LCS 長度是否跟 s.length() 一樣就好，$\mathcal{O}(NM)$
另一個做法就是雙指標直接看 s 是否都在 t 裏頭就好 $\mathcal{O}(N+M)$

N=s.length, M=t.length

AC Code#

Copy

class Solution {
public:
    
    int dp[105][10005];
    inline bool buildDP(string &a, string &b)
    {
        memset(dp, 0, sizeof(dp));
        
        for(int i = 1; i <= a.size(); i++)
            for(int j = 1; j <= b.size(); j++)
            {
                if(a[i-1] == b[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        
        // for(int i = 0; i <= a.size(); i++)
        //     for(int j = 0; j <= b.size(); j++)
        //         printf("%d%s", dp[i][j], (j==b.size()?"\n":""));
 
        return dp[a.size()][b.size()] == a.size();
    }
    
    bool followUp(string &a, string &b)
    {
        int i=0, j=0;
        while(i < a.size() && j < b.size())
        {
            if(a[i] == b[j])
                i++;
            j++;
        }
        return i == a.size();
    }
    
    bool isSubsequence(string s, string t)
    {
        return followUp(s, t);
    }
};

view raw leetcode/392.cpp delivered with ❤ by emgithub

賞析#

• 只有三行的雙指標
  • https://leetcode.com/problems/is-subsequence/discuss/87272/3-lines-C

心得#

看到 subsequence 直覺就想到 LCS 但題目好像不是問這個