392.md

✏️基础刷题之(392. Is Subsequence)

. 2020-07-15 星期二 开始吧 库里的深夜食堂

✏️描述

给定字符串 s 和 t，判断 s 是否是 t 的子序列。子序列的意思是此字符串是由原字符不删或者删除一些中间字符而不改变原有的字符位置而形成的新字符串。

✏️题目实例

​

---

✏️题目分析

最直观的解法，常人思维，一一对比。直接遍历字符串 s 然后一一在 t 中对比，如果存在，就记录下此字符在 t 中的下标 index，等对比下一位字符的时候，就从 t 的 index +1 开始，只要一个不存在，说明 s 不是 t 的子序列。

✏️解法一

/**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isSubsequence($s, $t)
{
        $index = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            $index = strpos($t, $s[$i], $index);
            if ($index === false) {
                return false;
            }
            $index++;
        }
        return true;
    }

✏️解法二

时间复杂度上可以从 O(n2) 到 O(n)。 还是很常规的做法。可以用两个指针 i,j 分别表示 s 和 t 的位置，遍历字符串，只要当前位置两个字符串相等，那么 i 和 j 同时递增，否则 j 单独自增。最后只需要判断 i 是否等于 s 的长度即可。时间复杂度 O(n)。

/**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isSubsequence($s, $t)
{
        $i = 0;
        for ($j = 0; $j < strlen($t) && $i < strlen($s); $j++) {
            if ($s[$i] === $t[$j]) $i++;
        }
        return $i === strlen($s);
    }

联系

​