392. 判断子序列

;(function () {
  /**
   * 392. 判断子序列
   * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
   * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
   * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
   *
   * 进阶：
   * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
   *
   * 输入：s = "abc", t = "ahbgdc"
   * 输出：true
   *
   * 输入：s = "axc", t = "ahbgdc"
   * 输出：false
   *
   * 两个字符串都只由小写字符组成
   */

  function isSubsequence(s: string, t: string): boolean {
    // 方法一：
    // // 思路：遍历字符串s（比如abc），需要满足 a 的所有下标中必须有一个小于 b， b的所有下标中必须有一个小于 c。
    // let tArr: string[] = t.split('');
    // let sLen = s.length;
    // let arr: number[][] = [];
    // for (let i = 0; i < sLen; i++) {
    //     let tempArr: number[] = [];
    //     tArr.forEach((item, index) => {
    //         if (item === s[i]) {
    //             tempArr.push(index)
    //         }
    //     })
    //     arr.push(tempArr)
    // }
    // if (arr[0] && arr[0].length === 0) return false
    // // 2. 遍历二维数组
    // let curMinIndex: number = arr[0] ? Math.min(...arr[0]) : 0;
    // for (let j = 1; j < arr.length; j++) {
    //     // 上一个的最小下标值
    //     let filterMoreThan = arr[j].filter(item => item > curMinIndex);
    //     if (filterMoreThan && filterMoreThan.length > 0) {
    //         curMinIndex = Math.min(...filterMoreThan)
    //     } else {
    //         return false
    //     }
    // }
    // return true

    // 方法二：双指针
    let n = s.length,
      m = t.length
    let i = 0,
      j = 0
    while (i < n && j < m) {
      s[i] === t[j] && i++
      j++
    }
    return i === n
  }

  const s = 'abc',
    t = 'ahbgdc'
  const s1 = 'axc',
    t1 = 'accchbbbbgddc'
  const s2 = 'b',
    t2 = 'c'
  const s3 = 'aaaaaa',
    t3 = 'bbaaaa'
  console.log(isSubsequence(s, t))
  console.log(isSubsequence(s1, t1))
  console.log(isSubsequence(s2, t2))
  console.log(isSubsequence(s3, t3))
})()