判断子序列

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，392. Is Subsequence

先看题目描述

题目大意就是判断 s 是否为 t 的子序列，子序列的定义是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串

算法和思路

双指针法

第一反应就是双指针法，两个指针 left 和 right 起始分别指向字符串 s 和 t 的第 0 个字符，若 left 和 right 能匹配，就同时右移指针，若不匹配，就仅将 right 右移，若匹配中途 left 的值等于 s 长度，就直接返回 true；若最终 left 的值扔小于 s 长度，则返回 false

动态规划

看了题解才知道这题竟然还可以用动态规划，虽然性能不如双指针法，但这题可以用动态规划还是很惊讶的

  • 令 dp[i][j] 表示字符串 t 中从位置 i 开始往后字符 j 第一次出现的位置。在进行状态转移时，如果 t 中位置 i 的字符就是 j，那么 dp[i][j] = i，否则 j 出现在位置 i+1 开始往后，即 dp[i][j] = dp[i + 1][j]，因此我们要倒过来进行动态规划，从后往前枚举 i
  • 状态转移方程：若 t[i] = j，dp[i][j] = i；否则，dp[i][j] = dp[i + 1][j]
  • 用 n 表示字符串 t 长度，下标从 0 开始，那么应有 0 <= i < n，对于边界状态 dp[n - 1][…]，我们置 dp[n][…] 为 n，让 dp[n - 1][…] 能够正常转移，这样如果 dp[i][j] = n，就表示从位置 i 开始往后字符串 t 中不存在字符 j

算法源码

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (s.length() > t.length()) return false;
        int left = 0;
        int right = 0;
        while (right < t.length()) {
            if (t.charAt(right) == s.charAt(left)) left++;
            right++;
            if (left == s.length()) return true;
        }
        return false;
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m == 0) return true;
        if (m > n) return false;
        int[][] dp = new int[n+ 1][26];
        Arrays.fill(dp[n], n);
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) - 'a' == j) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int add = 0;
        for (int i = 0; i < m; i++) {
            if (dp[add][s.charAt(i) - 'a'] == n) return false;
            else add = dp[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }
}