Given two strings s and t, return true if _s is a subsequence of t, or false otherwise_.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Q: 判断字符串s是否是字符串t的子序列?
(注意:问的是子序列不是子串,子序列中元素不一定相邻,子串中元素则必须相邻。)
Constraints:
- 0 <= s.length <= 100
- 0 <= t.length <= 104
- s and t consist only of lowercase English letters.
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
解法1 直接比较(最快的)
class Solution {
public:
bool isSubsequence(string s, string t) {
/* s中的字符在t中可能是分散、重复的,但相对顺序一定是递增的。
* 定义count表示s中的字符在t中已出现的个数,
* 遍历t,如果下一个字符和s[count]一致,比较s和t的下一个字符(count++);
* 否则继续往下遍历t;
* 直到count=s.length()(是子序列)或者t遍历完毕(不是子序列)。
*
* 复杂度O(t.length())
*/
if(s.length() == 0){
return true; // 空s的是任何t的子序列
}
else if(t.length() == 0){
return false; // s不空,t空,肯定不是
}
int count=0, i=0;
for(int i=0; i<t.length(); i++){
if(s[count] == t[i]){
count++;
}
if(count >= s.length()){
return true;
}
}
return false;
}
};
运行效率评价
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Is Subsequence.
Memory Usage: 6.5 MB, less than 34.43% of C++ online submissions for Is Subsequence.
解法2 动态规划
class Solution {
public:
// 动态规划,复杂度O(m*n)
bool isSubsequence(string s, string t) {
// s和t的最长公共子序列的长度如果等于s的长度,那么s就是t的子序列
if(s.length() == 0){
return true; // 空s的是任何t的子序列
}
else if(t.length() == 0){
return false; // s不空,t空,肯定不是
}
else{
return this->lengthOfLongestCommonSequence(s, t) == s.length();
}
}
int lengthOfLongestCommonSequence(string& s, string& t){
// 动态规划求最长公共子序列的长度,不需要记录方向信息
int m=s.length(), n=t.length();
vector<vector<int>> dpArray(m+1, vector<int>(n+1, 0));
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s[i-1] == t[j-1]){
dpArray[i][j] = dpArray[i-1][j-1] + 1;
}
else{
dpArray[i][j] = max(dpArray[i-1][j], dpArray[i][j-1]);
}
}
}
return dpArray[m][n];
}
};
运行效率评价:
Runtime: 4 ms, faster than 28.25% of C++ online submissions for Is Subsequence.
Memory Usage: 8 MB, less than 9.05% of C++ online submissions for Is Subsequence.