0%

leetcode每日一题-判断子序列

Posted on In ,

判断子序列

image1

方法一：双指针

指针$i$指向$s$，指针$j$指向$t$，当s[i]==t[j]时，两个指针同时后移，否则就将$j$后移，如果$j$已经到$t$的末尾而$i$还未到$s$的末尾，返回false，否则返回true。

1
class Solution {
2
    public boolean isSubsequence(String s, String t) {
3
        if(s.length() == 0){
4
            return true;
5
        }
6
        int tindex = 0;
7
        int sindex = 0;
8
        while(tindex < t.length()){
9
            if(s.charAt(sindex) == t.charAt(tindex)){
10
                sindex++;
11
                tindex++;
12
            }else{
13
                tindex++;
14
            }
15
            if(sindex == s.length()){
16
                return true;
17
            }
18
        }
19
        return false;
20
        
21
    }
22
}

复杂度分析：

  • 时间复杂度：$O(m+n)$，$m$是$t$的长度，$n$是$s$的长度。
  • 空间复杂度：$O(1)$。

方法二：动态规划

如果是后续挑战中的情况，那么每次来一个序列$s$，就要重新比对，时间主要浪费在查找序列$t$上，我们可以用动态规划预处理一下$t$。令$dp[i][j]$表示从位置$i$开始字符$j$第一次出现的位置，那么转移方程为：

  1. 如果$t[i] == j$，那么$dp[i][j]=i$。
  2. 如果$t[i] \not= j$，那么$dp[i][j]=dp[i+1][j]$。

需要从后往前进行转移，边界条件是$dp[m][…]=m$，表示字符在位置$m$开始不存在。

1
class Solution {
2
    public boolean isSubsequence(String s, String t) {
3
        int m = t.length();
4
        int n = s.length();
5
        int k = 'z' - 'a';
6
        int[][] dp = new int[m+1][k];
7
        for(int i=0; i<k; i++){
8
            dp[m][i] = m;
9
        }
10
        for(int i=m-1; i>=0; i--){
11
            for(int j=0; j<k; j++){
12
                if(t.charAt(i) == j + 'a'){
13
                    dp[i][j] = i;
14
                }else{
15
                    dp[i][j] = dp[i+1][j];
16
                }
17
            }
18
        }
19
        int index = 0;
20
        for(int i=0; i<s.length(); i++){
21
            if(dp[index][s.charAt(i)-'a'] == m ){
22
                return false;
23
            }
24
            index = dp[index][s.charAt(i)-'a'] + 1;
25
        }
26
        return true;
27
    }
28
}

复杂度分析：

  • 时间复杂度：$O(m \times |\sum|+n)$，$\sum$是字符集。
  • 空间复杂度：$O(m \times |\sum|)$。