判断子序列
双指针
-
解题思路：
- 设置双指针 i , j 分别指向字符串 s , t 的首个字符，遍历字符串 t ：
- 当 s[i] == t[j] 时，代表匹配成功，此时同时 i++ , j++ ；
- 若 i 已走过 s 尾部，代表 s 是 t 的子序列，此时应提前返回 true ；
- 当 s[i] != t[j] 时，代表匹配失败，此时仅 j++ ；
- 若遍历完字符串 t 后，字符串 s 仍未遍历完，代表 s 不是 t 的子序列，此时返回 false；
![]( "判断子序列")
- 设置双指针 i , j 分别指向字符串 s , t 的首个字符，遍历字符串 t ：
-
复杂度：
- 时间复杂度： O(N)，其中 N 为字符串 t 的长度，最差情况下需完整遍历 t ；
- 空间复杂度： O(1)，i , j 变量使用常数大小空间；
-
代码实现：
var isSubsequence = function (s, t) { if (s.length == 0) return true; for (let i = 0, j = 0; j < t.length; j++) { if (s[i] === t[j]) { i++; if (i == s.length) // 若已经遍历完 s ，则提前返回 true return true; } } return false; }
动态规划
-
解题思路：
- 状态表示： 定义 dp[i][j] 表示字符串 s 的 [1,i] 区间和字符串 t 的 [1,j] 区间的最长公共子序列长度（下标从1开始）；
- 状态计算：可以根据 s[i] 和 t[j] 的情况，分为两种决策：
- 若 s[i] == t[j]，即两个字符串的最后一位相等，那么就转化成了字符串 s的[1,j-1] 区间和字符串 t 的[1,j-1] 区间的最长公共子序列长度再加上一，即 dp[i][j] = dp[i - 1][j - 1] + 1，（下标从1开始）；
![]( "判断子序列")
- 若 s[i] != t[j]，即两个字符串的最后一位不相等，那么字符串 s的[1,i] 区间在字符串 t 的[1,j] 区间的子序列长度无法延长，因此 dp[i][j] 就会继承 dp[i][j-1]，即 dp[i][j] = dp[i][j - 1]，（ 下标从1开始）；如图所示：比较 s[3] 与 t[3]，发现’f’不等于’e’，这样 dp[3][3] 无法在原先的基础上延长；因此继承 “acf"与"cf” 的值；即 dp[3][3] = dp[3][2]；
![]( "判断子序列")
- 若 s[i] == t[j]，即两个字符串的最后一位相等，那么就转化成了字符串 s的[1,j-1] 区间和字符串 t 的[1,j-1] 区间的最长公共子序列长度再加上一，即 dp[i][j] = dp[i - 1][j - 1] + 1，（下标从1开始）；
- 状态转移方程为：
- 当s[i] == t[j]：dp[i][j] = dp[i-1][j-1] + 1；
- 当s[i] != t[j]：dp[i][j] = dp[i][j - 1]；
- 初始化：
- dp[i][0] = dp[0][j] = 0；
- 空字符串与有长度的字符串的最长公共子序列长度肯定为 0；
- 实现细节：
- 前面定义的状态表示 dp 数组和 text 数组下标均是从 1 开始的，而题目给出的 text 数组下标是从 0 开始的；
- 为了一一对应，在判断 s 和 t数组的最后一位是否相等时，往前错一位，即使用s[i - 1]和 t[j - 1] 来判断；
-
代码实现：
const isSubsequence = (s, t) => { // s、t的长度 const [m, n] = [s.length, t.length]; // dp全初始化为0 const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0)); for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { // 更新dp[i][j]，两种情况 if (s[i - 1] === t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i][j - 1]; } } } // 遍历结束，判断 dp 右下角的数是否等于s的长度 return dp[m][n] === m ? true : false; };
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 分治基础
上一篇
评论
