392. 判断子序列 -- 双指针

àì夳堔傛蜴生んèń 2023-02-26 08:26 16阅读 0赞

[392][]. 判断子序列

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

你可以认为 `s` 和 `t` 中仅包含英文小写字母。字符串 `t` 可能会很长（长度 ~= 500,000），而 `s` 是个短字符串（长度 <=100）。

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

示例 1:  
`s = "abc", t = "ahbgdc"`

返回 `true`.

示例 2:  
`s = "axc", t = "ahbgdc"`

返回 `false`.

--------------------

# 解题思路 – 双指针 #

可以知道的是，当扫描`s`中的第  k k k 个字符时，假如它在`t`字符串中的第  i i i 位和第  j j j 位都出现过(  i i i  < < <  j j j)，那么我们从左到右扫描到第  i i i 位时，就认为已经找到了`s`中第  k k k 个字符。因为  i i i 后面有更多的备选字符可以用来找`s`中的剩余字符。也就是说，我们在`t`中找字符时，是严格不回溯的。这个问题可以使用双指针解决。

初始化指针  i i i ， j j j 为0，分别指向`s`和  j j j 的第0个字符，在`t`中找到s\[ i i i\]字符后， i i i\++试图找下一个字符。

若最后i到达`s`末尾，则说明找到了该字符串

public class Solution{
        
    
        public static boolean isSubsequence(String s, String t) {
        
            int p = 0;
            int q = 0;
    
            while(p < s.length() && q < t.length()){
        
                if(s.charAt(p) == t.charAt(q)){
        
                    p ++;
                    q ++;
                }else{
        
                    q ++;
                }
            }
    
            return p == s.length();
        }
    
    
        public static void main(String[] args) {
        
            String s = "axc";
            String t = "ahbgdc";
    
            boolean subsequence = Solution.isSubsequence(s, t);
            System.out.println(subsequence);
        }
    }

[392]: https://leetcode-cn.com/problems/is-subsequence/