leetcode 392. 判断子序列

水深无声 2023-07-03 08:22 17阅读 0赞

原题很简单，设一个双指针，遍历一下即可。

现在讨论一下：如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

当去匹配的s串很多的时候，再调用上面的方法其实不行。因为s串很短，最后的方法就是每次都只遍历一遍s。

具体做法：因为字符串只有26个字母，设dp\[i\]\[0\]表示当前位置后面，第一次出现字符a的位置，dp\[i\]\[1\]则表示第一次出现b的位置....所以，我们只要开一个dp\[n\]\[26\]的数组，然后遍历一遍t串即可。以后去匹配的时候，只需直接使用dp数组即可。

普通遍历：

class Solution {
    public:
        bool isSubsequence(string s, string t) {
            int i=0,j=0;
            int n1=s.size(),n2=t.size();
            while(i<n1&&j<n2)
            {
                if(s[i]==t[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    j++;
                }
            }
            return i==n1;
        }
    };

处理大数据：

class Solution {
    public:
        bool isSubsequence(string s, string t) {
            t.insert(t.begin(),' ');
            int n=t.size();
            int dp[n+3][26];
            for(int ch=0;ch<26;ch++)
            {
                int nxt=-1;
                for(int i=n-1;i>=0;i--)
                {
                    dp[i][ch]=nxt;
                    if(t[i]-'a'==ch)
                    {
                        nxt=i;
                    }
                }
            }
            int i=0;
            for(auto ch:s)
            {
                i=dp[i][ch-'a'];
                if(i==-1) return false;
            }
            return true;
        }
    };