算法 | 判定字符串的子序列

审题

这是力扣上的一道算法题（392. 判断子序列^[1]）。判断给定的字符串 s（较短）是否是字符串 t（较长）的子序列。

“子序列”和“子串”是 2 个概念，要注意区分。

举个例子。

如果说 s 是 t 的 “子串”，就表示 t.includes(s) 返回 true。

而 “子序列” 只是表示 s 中每个字符的出现顺序跟 t 中是一样的。比如，虽然 "abcde".includes("ace") 返回 false，但 “ace” 就是 “abcde” 的一个子序列。

也就是说，如果 s 是 t 的 “子串”，那么 s 必然也是 t 的 “子序列”，反之就不行。

理解了“子序列”的概念，就可以做题了。

函数定义如下。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
  // ...
}

分析

我的思路是，在遍历 t 中每个字符时，我们就能判定 s 是否使它的子序列了。

假设，要判定的 s 是 “ace”，t 是 “abcde”。

首先，声明 2 个索引 i 和 j，初始值都为 0。

 ↓i
"ace"
"abcde"
 ↑j

i 表示当前 “ace” 中要匹配的字符索引，j 则表示当前 “abcde” 正在遍历的字符索引。

此时，i 和 j 所处索引位置都为 “a”，匹配！i 和 j 同时进 1。

  ↓i
"ace"
"abcde"
  ↑j

“c” 和 “b” 不等。i 不变，j 进 1。

  ↓i
"ace"
"abcde"
   ↑j

“c” 和 “c” 相等，匹配！i 和 j 同时进 1。

   ↓i
"ace"
"abcde"
    ↑j

“e” 和 “d” 不等。i 不变，j 进 1。

   ↓i
"ace"
"abcde"
     ↑j

“e” 和 “e” 相等，匹配！i 和 j 同时进 1。

     ↓i
"ace"
"abcde"
       ↑j

遍历结束。

此时，i 的值等于 3，表示 “ace” 中的字符都匹配完成，说明 “ace” 是 “abcde” 的子序列。

实现

按照这个思路，我们来写代码。

var isSubsequence = function(s, t) {
  let i = j = 0
  
  for (; j < t.length; j++) {
    if (t[j] === s[i]) {
      i++
    }
  }
  
  if (i === s.length) {
    return true
  } else {
    return false
  }
}

甚至都不需要索引 j。

var isSubsequence = function (s, t) {
    let i = 0

    for (let char of t) {
        if (char === s[i]) {
            i++
        }
    }

    if (i === s.length) {
        return true
    } else {
        return false
    }
};