97 - 判断子序列

题目

给定字符串 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.

后续挑战 :

如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解答

既然相对位置不能改变，那么就一个个遍历咯。。

直接遍历

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

Runtime: 68 ms, faster than 62.67% of JavaScript online submissions for Is Subsequence.

Memory Usage: 38.9 MB, less than 66.67% of JavaScript online submissions for Is Subsequence.

func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    for j < len(t) && i < len(s) {
        if s[i]==t[j] {
            i++
        }
        j++
    }
    if i != len(s) {
        return false
    } else {
        return true
    }
}

Runtime: 12 ms, faster than 85.80% of Go online submissions for Is Subsequence.

Memory Usage: 6.4 MB, less than 100.00% of Go online submissions for Is Subsequence.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        while j < len(t) and i < len(s):
            if s[i] == t[j]:
                i += 1
            j += 1
        if i != len(s):
            return False
        else:
            return True

Runtime: 284 ms, faster than 15.19% of Python3 online submissions for Is Subsequence.

Memory Usage: 18.3 MB, less than 26.67% of Python3 online submissions for Is Subsequence.

class Solution {
  public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (j < t.length() && i < s.length()) {
      if (s.charAt(i) == t.charAt(j)) {
        i++;
      }
      j++;
    }
    if (i != s.length()) {
      return false;
    } else {
      return true;
    }
  }
}

Runtime: 6 ms, faster than 86.69% of Java online submissions for Is Subsequence.

Memory Usage: 48.1 MB, less than 100.00% of Java online submissions for Is Subsequence.

用index

作者：cartoon

链接：https://leetcode-cn.com/problems/is-subsequence/solution/ji-yu-qian-yi-yuan-su-de-wei-zhi-dui-bi-by-cartoon/

var isSubsequence = function (s, t) {
  let index = -1
  for (const item of s) {
    index = t.indexOf(item, index + 1)
    if (index === -1) {
      return false
    }
  }
  return true
};

Runtime: 64 ms, faster than 78.14% of JavaScript online submissions for Is Subsequence.

Memory Usage: 38 MB, less than 100.00% of JavaScript online submissions for Is Subsequence.

迭代器

作者：leacoder 链接：https://leetcode-cn.com/problems/is-subsequence/solution/python3shi-xian-chang-gui-shuang-zhi-zhen-jie-fa-j/

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        b = iter(t)
        return all(((i in b) for i in s))

Runtime: 56 ms, faster than 81.78% of Python3 online submissions for Is Subsequence.

Memory Usage: 18.5 MB, less than 26.67% of Python3 online submissions for Is Subsequence.

看不懂的骚操作😂😂😂