20200727-392.is-subsequence.md

#392.is-subsequence

题目链接：https://leetcode-cn.com/problems/is-subsequence/

参考链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-le-2/

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例1：

s = "abc", t = "ahbgdc"

返回 true.

示例2：

s = "axc", t = "ahbgdc"

返回 false.

解题

思路[1]遍历+jsAPI

• 一次遍历，使用indexOf查找位置
• 可以使用indexOf的第二参数限制查找范围为上一次查找之后，也可以使用字符串剪切把上次查找到位置之前的字符串剪掉

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
  let i = 0, prev = -1;
  while(i < s.length){
    let index = t.indexOf(s[i], prev+1);
    if(index === -1){
      return false
    }
    prev = index;
    i++;
  }
  return true
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
  let str = t;
  for(let c of s){
  	const index = str.indexOf(c);
  	if(index <= -1){
  		return false;
  	}
  	str=str.substring(index+1);
  }

  return true;
};

思路[2]双指针

• 两个指针，分别指向s和t，如果两个指针指向的字符相等，则移动指向s的指针，否则只移动指向t的指针，如果最后指向s的指针移到了最后，则说明存在相等
• 简单的双指针问题，就是遍历比较

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
  let i = 0, j = 0, m = t.length, n = s.length;
  while(i < m && j < n){
    if(t[i] === s[j]){
      j++;
    }
    i++;
  }
  return j === n
};

思路[3]动态规划

• 一共26个小写字母，一共m个字符，可以预先生成一个动态规划的状态数组，使查询结果变为数组中直接查询值，如果字符够长，使用这个方法比较省时
• 数组dp位置记录字符出现的位置，dp[i][j]表示在i位置以后j字符第一次出现的位置(包括i)
• 状态转移方程，对于每一个dp[i][j]存在
  • 如果i位置的字符就是j字符，则dp[i][j] = i
  • 如果不相等，则取后一个位置(i+1)的结果，即，dp[i][j] = dp[i+1][j]
• 边界值，如果到最后都没有出现该字符，则字符出现的位置为字符长度m
• 状态转移数组的建立是从后往前遍历的，每次的状态是由后面决定的，因为我们如果找到一个字符在字符串出现，则下次判断，需要在这个找到的字符的位置以后再找下一个字符。

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
  let m = t.length, n = s.length, dic = [];
   dp[m] = []
  for(let i = 0; i < 26; i++){
    dp[m][i] = m
  }
  for(let i = m - 1; i >= 0; i--){
    dic[i] = []
    for(let j = 0; j < 26; j++){
      if(j === (t[i].charCodeAt(0)-97)){
        dp[i][j] = i;
        continue;
      }
      dp[i][j] = dp[i+1][j]
    }
  }
  let pos = 0
  for(let i = 0; i < n; i++){
    let next = dp[pos][(s[i].charCodeAt(0)-97)];
    if(next === m){
      return false
    }
    pos = next + 1
  }
  return true
};

思考

• 有时不一定要在动态规划的过程和状态数组中直接找到结果，可以通过状态数组再次加工拿到我们想要的结果