判断子序列


判断子序列

题目

1
2
3
4
5
6
7
8
9
10
给定字符串 s 和 t ,判断 s 是否为 t 的子序列
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串

示例 1:
输入:s = "abc", t = "ahbgdc"
输出:true

示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false

解法

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
思路:
同时遍历两个字符串,字符串s只有在遍历t的过程中存在才会继续遍历,否则s不动,如果s和t其中一个遍历完成
查看s是否遍历完成,是返回true,否返回false

代码:
/**
* @param String $s
* @param String $t
*
* @return Boolean
*/
function isSubsequence($s, $t)
{
$i = 0;
$j = 0;
$n = strlen($s);
$m = strlen($t);
// 遍历直到s,t其中一个字符串遍历完成
while ($i < $n && $j < $m) {
if ($s[$i] === $t[$j]) {
// 如果查询到符合条件的字符,遍历s的下一个字符
$i++;
}

// t一直在遍历
$j++;
}

// 如果$i等于字符串的长度,证明s字符串完全遍历,且所有的字符都在t中存在
return $i === $n;
}