题目地址: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;
}
看了一下,不仅平平无奇的官方答案碾压我,更是和评论区大佬拉的遥远,算法之路真的还有很长啊!