392.判断子序列
要求：
判断第一个字符串是否是第二个字符串的子序列
思路1：
设置成deque，如果长度为0则是
代码1：
1 // 要求： 判断s 是否是t的子序列 2 // 思路： 将s作为queue，如果头相等，那么就弹出，遍历后，查看是否为0 3 // 4 bool isSubsequence_simple(string s, string t) { 5 deque<char> s_(s.begin(), s.end()); 6 7 for (int i = 0; i < t.size(); i++) 8 { 9 if (t[i] == s_.front()) 10 { 11 s_.pop_front(); 12 } 13 } 14 15 return s_.empty(); 16 }
思路2：
求这两个的最长公共子序列，如果长度==第一个字符串长度，则是
代码2：
1 bool isSubsequence(string s, string t) { 2 vector<vector<int>>dp(s.size() + 1, vector<int>(t.size() + 1, 0)); 3 int result = 0; 4 5 for (int i = 1; i <= s.size(); i++) 6 { 7 for (int j = 1; j <= t.size(); j++) 8 { 9 if (s[i - 1] == t[j - 1]) 10 dp[i][j] = dp[i - 1][j - 1] + 1; 11 else 12 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 13 14 result = result > dp[i][j] ? result : dp[i][j]; 15 } 16 } 17 18 return result == s.size(); 19 }