【LeeCode】392. 判断子序列

【题目描述】

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

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

进阶：

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

致谢：

特别感谢 ​​@pbrother ​​添加此问题并且创建所有测试用例。

【示例】

【代码1】admin

admin: 测试用例 16/18

这里提供了一个思路就是： 依次便利sss里的字符, 采用了index记录了下标,只要依次递增且count等于sss的字符长度就是ok的

但有个问题就是类似“ab”这种依次递增的, 在“baab”里返回'b'的下标是0, 所以代码校验有问题

package com.company;
import java.util.*;

class Solution {
    public boolean isSubsequence(String sss, String str) {
        boolean flag = false;
        int index = -1;
        int count = 0;
        for (int i = 0; i < sss.length(); i++) {
            char c = sss.charAt(i);
            if (str.contains(c+"")){
                int tmp = str.indexOf(c);
                if (tmp > index){
                    index = tmp;
                    count++;
                }else {
                    index = 0;
                    count = 0;
                }
            }
        }
        if (count == sss.length()){
            flag = true;
        }else{
            flag = false;
        }
        return flag;
    }
}
public class Test {
    public static void main(String[] args) {
        String sss = "abc";
        String sss1 = "axc";
        String str = "ahbgdc";
        System.out.println(new Solution().isSubsequence(sss, str));   // ture
        System.out.println(new Solution().isSubsequence(sss1, str));  // false

        String s = "aaaaaa";
        String t = "bbaaaa";
        System.out.println(new Solution().isSubsequence(s, t));       // false

        String ss = "ab";
        String st = "baab";
        // 代码有点问题, 这里ss第2个字符'b'在st中输出index是0 导致逻辑判断异常
        System.out.println(new Solution().isSubsequence(ss, st));       // true
    }
}

【代码2】简单

这里的聪明之处在于，每次的indexOf都是递增了1  说明了sss里面的每个字符都是一次递增在str里查找是否有无

最简单的,也是最快的,在字符串s上顺序查找一个word的每一个字符即可!

package com.company;
import java.util.*;

class Solution {
    public boolean isSubsequence(String sss, String str) {
        int index = -1;

        for(char x: sss.toCharArray()){
            index = str.indexOf(x, index + 1);
            if (index < 0) return false;
        }
        return true;
    }
}
public class Test {
    public static void main(String[] args) {
        String sss = "abc";
        String sss1 = "axc";
        String str = "ahbgdc";
         System.out.println(new Solution().isSubsequence(sss, str));  // ture
         System.out.println(new Solution().isSubsequence(sss1, str));  // false

        String s = "aaaaaa";
        String t = "bbaaaa";
        System.out.println(new Solution().isSubsequence(s, t));  // false
    }
}

【代码3】双指针

package com.company;
import java.util.*;

class Solution {
    public boolean isSubsequence(String sss, String str) {
        int n = sss.length();
        int m = str.length();

        int i = 0;
        int j = 0;

        while ( i < n && j < m){
            if (sss.charAt(i) == str.charAt(j)){
                i++;
            }
            // 如果匹配不到,str是最长的字符 所以递增
            j++;
        }
        // 如果最后i递增到了sss的长度 则返回true
        return i == n;
    }
}
public class Test {
    public static void main(String[] args) {
        String sss = "abc";
        String sss1 = "axc";
        String str = "ahbgdc";
        System.out.println(new Solution().isSubsequence(sss, str));   // ture
        System.out.println(new Solution().isSubsequence(sss1, str));  // false

        String s = "aaaaaa";
        String t = "bbaaaa";
        System.out.println(new Solution().isSubsequence(s, t));       // false

        String ss = "ab";
        String st = "baab";
        System.out.println(new Solution().isSubsequence(ss, st));       // true
    }
}