题目描述
双指针解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size();
int n = t.size();
int i = 0, j = 0;
while(i < m && j < n)
{
if(s[i] == t[j])
{
++i;
}
++j;
}
if(m == i)
return true;
return false;
}
};
|
时间复杂度：Max(O(m), O(n))
空间复杂度：O(1)
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
bool isSubsequence(string s, string t) {
int row = s.size() + 1;
int col = t.size() + 1;
vector<vector<bool>> dp;
dp.resize(row);
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
dp[i].resize(col);
dp[i][j] = i == 0 ? true : false;
}
}
for (int i = 1; i < row; ++i)
{
for (int j = 1; j < col; ++j)
{
if (dp[i][j - 1] == true)
{
dp[i][j] = true;
}
else if (s[i - 1] == t[j - 1] && dp[i - 1][j - 1] == true)
{
dp[i][j] = true;
}
else
{
dp[i][j] = false;
}
}
}
return dp[row - 1][col - 1];
}
};
|
时间复杂度：O(mn)
空间复杂度：O(mn)
