双指针
思路分析
- 使用双指针 sIndex 和 tIndex 分别指向字符串 s 和 t。
- 遍历 t，如果 s 当前字符和 t 当前字符相同，sIndex 右移，tIndex 始终右移。
- 最后判断 sIndex 是否等于 s 的长度，如果是则 s 是 t 的子序列。
代码实现
publicbooleanisSubsequence(Strings,Stringt){// 1. 定义指针i,j分别指向s,t的第一个元素inti=0;intj=0;// 2. 遍历字符串t，校验字符串s的每个字符是否都在t中while(i<s.length()&&j<t.length()){if(s.charAt(i)==t.charAt(j)){i++;}j++;}// 3. 如果i指针遍历完了s字符串，说明s是t的子序列returni==s.length();}复杂度分析
- 时间复杂度为 O(n)，这里 n 是字符串 t 的长度。
- 空间复杂度为O(1)
动态规划
思路分析
- 定义一个二维数组 dp[i][j]，其中 i 表示字符串 s 的前 i 个字符，j 表示字符串 t 的前 j 个字符。dp[i][j] 的值为 true 表示 s 的前 i 个字符是 t 的前 j 个字符的子序列，否则为 false。
- 初始化 dp[0][j] 为 true，因为空字符串是任何字符串的子序列。
- 状态转移方程为：
- 如果 s[i - 1] == t[j - 1]，那么 dp[i][j] = dp[i - 1][j - 1]，表示如果当前字符相等，s 的前 i 个字符是 t 的前 j 个字符的子序列当且仅当 s 的前 i - 1 个字符是 t 的前 j - 1 个字符的子序列。
- 如果 s[i - 1] != t[j - 1]，那么 dp[i][j] = dp[i][j - 1]，表示如果当前字符不相等，s 的前 i 个字符是 t 的前 j 个字符的子序列当且仅当 s 的前 i 个字符是 t 的前 j - 1 个字符的子序列。
- 最终 dp[s.length()][t.length()] 的值即为所求。
代码实现
publicbooleanisSubsequence2(Strings,Stringt){intm=s.length();intn=t.length();boolean[][]dp=newboolean[m+1][n+1];for(intj=0;j<=n;j++){dp[0][j]=true;}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=dp[i][j-1];}}}returndp[m][n];}复杂度分析
- 时间复杂度为O(m∗n)，其中 m 是字符串 s 的长度，n 是字符串 t 的长度，因为需要填充一个 m * n 的二维数组。
- 空间复杂度为 O(m∗n)，即二维数组的大小。
