判断子序列 忘是亡心i 2024-04-03 09:07 8阅读 0赞 ### 392. 判断子序列 ### > 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 > 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。 ##### 进阶: ##### > 如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码? ##### 示例 1: ##### > 输入:s = “abc”, t = “ahbgdc” > 输出:true ##### 示例 2: ##### > 输入:s = “axc”, t = “ahbgdc” > 输出:false ##### 提示: ##### 0 < = s . l e n g t h < = 100 0 <= s.length <= 100 0<=s.length<=100 0 < = t . l e n g t h < = 1 0 4 0 <= t.length <= 10^4 0<=t.length<=104 两个字符串都只由小写字符组成。 两个字符串都只由小写字符组成。 两个字符串都只由小写字符组成。 ##### 代码1(Java): ##### public class child_str { public static void main(String[] args) { // TODO 自动生成的方法存根 String s = "abc"; String t = "ahbgdc"; System.out.println(isSubsequence(s,t)); } public static 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; } } ##### 代码2(Java): ##### public class child_str { public static void main(String[] args) { // TODO 自动生成的方法存根 String s = "abc"; String t = "ahbgdc"; System.out.println(isSubsequence(s,t)); } public static boolean isSubsequence(String s, String t) { int index = -1; for (char c : s.toCharArray()) { index = t.indexOf(c, index + 1); System.out.print(c); System.out.println(index); if (index == -1) { return false; } } return true; } } ##### 复杂度分析 ##### * 时间复杂度:O(n+m),其中 n为 s 的长度,m为 t 的长度。每次无论是匹配成功还是失败,都有至少一个指针发生右移,两指针能够位移的总距离为 n+m。 * 空间复杂度:O(1)。 题目来源:[力扣(LeetCode)][LeetCode] 注:仅供学习参考。 [LeetCode]: https://leetcode.cn/problems/is-subsequence
还没有评论,来说两句吧...