当前位置: 面试刷题>> 判断子序列(经典算法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` 的一个子序列。