392. 判断子序列

Problem: 392. 判断子序列

思路

如图所示我们只要从t中找到了对应的字母s[i],并且该字母在t中的索引大于他前面的字母s[i-1]在t中的索引,就可以确定s[0..i]是t的子序列。

我们可以用下面方法

• 先查找第一个字母s[0]在t中的索引,存入map中。

• 从1开始遍历s。

  • 在t中找t[map[s[i-1]]+1...end]的子字符串中有没有s[i],map[s[i-1]+1]就是s[i-1]在t中的索引的后面一个。
  • 找到了则说明s[0..i]是t的子序列
    • 记录s[i]在t中的索引 因为我们是取出子序列查找的 所以要记得加上子串的开头的索引
  • 否则 直接 return false

• 循环结束 说明s[0...end]是t的子序列

• return false

Code

[]

class Solution {
public:
    bool isSubsequence(string s, string t) {
        unordered_map<char,int> map;
        if(s=="")return true;
        //dp[i] 表示[0...i]是否是t的子序列
        //在t中查找s的第一个字符有没有
        int index = t.find(s[0]);
        if(index!=-1)  map[s[0]]=index;
        else return false;
        for(int i=1;i<s.size();i++) {
           //查找t[map[s[i-1]]...end]]有没有s[i]
           //也就是在t中找s[i-1]位置之后子字符串中有没有s[i]
           string sub=t.substr(map[s[i-1]]+1,t.size()-map[s[i-1]]-1);
           cout << sub << endl;
           int index=sub.find(s[i]);
           //有则记录index index要加上s[i-]的位置 因为我们是取出子序列查找的 
           if(index!=-1) map[s[i]]=index+map[s[i-1]]+1;
           else return false;
        }
        return true;
    }
};