当前位置: 面试刷题>> 判断子序列(经典算法150题)


### 完整题目描述 **题目:判断子序列** 给定两个字符串 `s` 和 `t`,编写一个函数来判断 `t` 是否是 `s` 的一个子序列。 一个字符串的子序列是指,从原始字符串中删除一些(也可以不删除)字符而不改变剩余字符的相对位置形成的字符串(即,`t` 可以从 `s` 中通过删除某些字符而不改变 `t` 中字符的相对顺序得到)。 **示例 1**: ``` 输入: s = "abc", t = "ahbgc" 输出: true ``` 解释: `t` 可以是 `s` 的一个子序列,通过删除 `s` 中的字符 'b' 和 'd' 来获得。 **示例 2**: ``` 输入: s = "axc", t = "ahbgc" 输出: false ``` **注意**: - 你可以假设所有字符串都只包含小写字母。 - 字符串的长度不会超过 256。 ### PHP 示例代码 ```php function isSubsequence($s, $t) { $sLen = strlen($s); $tLen = strlen($t); $i = 0; // 指向s的指针 for ($j = 0; $j < $tLen; $j++) { if ($i < $sLen && $s[$i] === $t[$j]) { $i++; } } // 如果s的指针走到了末尾,说明t是s的子序列 return $i === $sLen; } // 测试代码 echo isSubsequence("abc", "ahbgc") ? "true" : "false"; // 输出: true echo isSubsequence("axc", "ahbgc") ? "true" : "false"; // 输出: false ``` ### Python 示例代码 ```python def isSubsequence(s: str, t: str) -> bool: i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s) # 测试代码 print(isSubsequence("abc", "ahbgc")) # 输出: True print(isSubsequence("axc", "ahbgc")) # 输出: False ``` ### JavaScript 示例代码 ```javascript function isSubsequence(s, t) { let i = 0, j = 0; while (i < s.length && j < t.length) { if (s[i] === t[j]) { i++; } j++; } return i === s.length; } // 测试代码 console.log(isSubsequence("abc", "ahbgc")); // 输出: true console.log(isSubsequence("axc", "ahbgc")); // 输出: false ``` 在以上代码中,我们通过两个指针(`i` 和 `j`)分别在字符串 `s` 和 `t` 上进行遍历。当发现 `s[i]` 等于 `t[j]` 时,我们增加 `i` 的值。无论是否相等,我们都会增加 `j` 的值以继续遍历 `t`。如果最终 `i` 等于 `s` 的长度,那么说明 `t` 是 `s` 的一个子序列。
推荐面试题