🌕🌕 392. 判断子序列

难度: 🌕🌕

问题描述

---

解法 1 - 双指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 思路：
        // 双指针
        int rows = s.length();
        int cols = t.length();
        int m = 0; 
        int n = 0;
        while(m < rows && n < cols) {
            if(s.charAt(m) == t.charAt(n)) {
                m ++;
                n ++;
            } else {
                n ++;
            }
        }
        return m == rows;
    }
}

---

输出 1

---

解法 2 - dp

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 思路：
        // dp[i][j] = dp[i][j - 1], dp[i - 1][j - 1]
        int rows = s.length();
        int cols = t.length();
        boolean[][] dp = new boolean[rows + 1][cols + 1];
        // 初始化
        for(int j = 0; j <= cols; j ++) {
            dp[0][j] = true;
        }
        // dp
        for(int i = 1; i <= rows; i ++) {
            for(int j = 1; j <= cols; j ++) {
                int m = i - 1;
                int n = j - 1;
                if(s.charAt(m) == t.charAt(n)) {
                    dp[i][j] |= dp[i - 1][j - 1];
                }
                dp[i][j] |= dp[i][j - 1];
            }
        }
        return dp[rows][cols];
    }
}

---

输出 2

---

解法 3 - 进阶问题

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 思路：
        // 进阶问题
        // 常规情况下，我们需要同时遍历 s & t 直到一方截止，最差情况下遍历 t 的长度
        // 如果 t 不变，s 需要经常和 t 匹配，那么我们可以预先对 t 进行一些前置处理，使得判断时可以跳跃着匹配，只需遍历 s 的长度
        // 那么如何做？
        // 假设遍历 s 的 cur 时对应 t 的下标为 index，我们想要快速得到 s 下一个字符 next 对应 t 所在下标
        // 因此需要存储 t 的任意下标处到任意字符的下标
        // 例 s = bac， t = ababc
        // s 想要 b，我们需要快速得到 t 中第一个 b 所在下标， 为 1
        // s 想要下一个字符 a，我们在 t 当前下标 1 处快速得到从这里出发，后续的第一个 a 所在下标，即 2
        // s 想要下一个字符 c，我们在 t 下标 2 处快速得到从 2 以后的第一个 c 所在下标，即 4
        // s 遍历完成，满足条件
        int m = s.length();
        // 对 t 进行预处理
        t = " " + t; // 由于 s 的首个字符并不一定对应 t 的首个字符，我们需要找到 s 首字符对应 t 的首字符位置
        int n = t.length();
        // 因此需要添加一个入口字符，这个入口字符，含有到 s 的 26 种任意起始字符的路径下标
        int[][] arr = new int[n][26];
        // 如果外层遍历 t 的下标，复杂度为 O(N)，内层找 [a - z] 所有可能情况字符的下标，仍需要遍历一遍 t，复杂度为 O(N)
        // 若外层遍历 [a - 1] 所有可能情况的字符，复杂度为 O(26)，内层遍历 t 的下标，找该下标处下一个字符的下标，复杂度为 O(N)
        // 所以采用 外层遍历 字符，内层遍历 t 的方式填充 arr[]
        for(char c = 'a'; c <= 'z'; c ++) {
            // 当前要寻找的下标为 c
            int y = c - 'a'; // 对应 arr 的纵坐标
            int val = -1; // 如果从 t 的某个下标之后不会出现 c，则 val == -1 表示没有
            // 从后往前遍历
            for(int i = n - 1; i >= 0; i --) {
                char cur = t.charAt(i);
                arr[i][y] = val; 
                if(cur == c) {
                    // 当前下标处的字符与想要寻找的字符匹配，那么再往前遇到该字符，下标更新为当前下标
                    val = i;
                }
            }
        }
        // 遍历 s
        int index = 0; // t 的初始下标，对应 ' '，里面存放了 26 种字符的入口下标
        for(int i = 0; i < m; i ++) {
            char c = s.charAt(i); // 想要查找的字符
            // 到 t 中查找，初始时从 下标 0 的 ' ' 入口找到初始下标
            index = arr[index][c - 'a'];
            if(index == -1) {
                return false; // 说明 t 从当前下标查找，往后不存在 s 想要的字符 c
            }
        }
        return true;
    }
}

---

输出 3