脚撕LeetCode(392)Easy

题目地址：https://leetcode-cn.com/problems/is-subsequence/submissions/

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。 （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 进阶： 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。 在这种情况下，你会怎样改变代码？ https://leetcode-cn.com/problems/is-subsequence/submissions/

示例 1： 输入：s = "abc", t = "ahbgdc" 输出：true 示例 2： 输入：s = "axc", t = "ahbgdc" 输出：false 提示： 0 <= s.length <= 100 0 <= t.length <= 10^4 两个字符串都只由小写字符组成。 https://leetcode-cn.com/problems/is-subsequence/submissions/

一、爆破法

这里先想到的是双指针法，通过双指针的遍历最终得出是否具备需要的字符

（这里没有想到的是，官方答案多了一个步骤 就是把t.length和s.length用变量保存下来了（比我的办法节省了1ms）

执行结果如下：

16 / 16 个通过测试用例

状态：通过

执行用时: 2 ms

内存消耗: 35.9 MB

public boolean isSubsequenceMe(String s, String t) {
    if (s.length() > t.length()) return false;
    int tIndex = 0;
    int sIndex = 0;
    while (tIndex < t.length() && sIndex < s.length()) {
        if (t.charAt(tIndex) != s.charAt(sIndex)) {
            tIndex++;
            continue;
        }
        tIndex++;
        sIndex++;
    }
    return sIndex == s.length();
}

二、官方答案

官方答案使用的也是双指针法，唯一不同的是他的t.length和s.length保存下来，时间比我少了1ms

执行结果如下：

16 / 16 个通过测试用例

状态：通过

执行用时: 1 ms

内存消耗: 35.8 MB

public boolean isSubsequence(String s, String t) {
    int n = s.length(), m = t.length();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == n;
}

三、评论区大佬法

这个就厉害了，一看就是我对api的熟悉程度不高，没想到评论区大佬用到了String.indexOf的精髓，可以indexOf(String,int)来表示第几个字符后的第一个我要的字符的下标，如果为-1说明找不到（0ms)

执行结果如下：

16 / 16 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 36.1 MB

public static boolean isSubsequence2(String s, String t) {
    char[] arr = s.toCharArray();
    int j = -1;
    for(int i = 0;i<arr.length;i++) {
        j = t.indexOf(arr[i],j+1);
        if(j==-1) {
            return false;
        }
    }
    return true;
}

看了一下，不仅平平无奇的官方答案碾压我，更是和评论区大佬拉的遥远，算法之路真的还有很长啊！