【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
    }
}