判断子序列

忘是亡心i 2024-04-03 09:07 56阅读 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