https://leetcode-cn.com/problems/is-subsequence/
双指针法
<?php
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isSubsequence($s, $t) {
$tLen = strlen($t);
$sLen = strlen($s);
$sLoc = 0;
for ($tLoc = 0; $tLoc < $tLen; $tLoc++) {
if ($sLoc >= $sLen) {
return true;
}
if ($t[$tLoc] == $s[$sLoc]) {
$sLoc++;
}
}
return $sLoc >= $sLen;
}
}
动态规划
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isSubsequence2($s, $t) {
// f[i][j] = f[i+1][j] i != j
// f[i][j] = i; i=j
// 动态规划,先计算出每一个字符后面最先出现另外一个字符
$dp = [];
for ($i = 0; $i < 26; $i ++) {
$dp[strlen($t)][$i] = strlen($t);
}
// 初始化一个二维数组,数组是 strlen($t) * 26 的二维数组
// 每一个元素的 $i 指 $t 字符串的第几个字符
// 每一元素的 $j 指从 $i 位置到 $j 位置
// 值为下一个 $j 位置的 index, 如果$i 位置就是 $j 那就是自己
for ($i = strlen($t) - 1; $i >= 0; $i--) {
for ($j = 0; $j < 26; $j++) {
if (ord($t[$i]) == $j) {
$dp[$i][$j] = $i;
} else {
$dp[$i][$j] = $dp[$i+1][$j];
}
}
}
$curIndex = 0;
for ($i = 0; $i < strlen($s); $i++) {
if ($dp[$curIndex][ord($s[$i])] == strlen($t)) {
return false;
} else {
$curIndex = $dp[$curIndex][ord($s[$i])] + 1;
}
}
return true;
}
动态规划的转移方程建议看一下官方题解,说的比较清楚
// f[i][j] = f[i+1][j]; i != j
// f[i][j] = i; i=j