不同的子序列問題I

作者：Grey

題目連結

暴力解法

定義遞迴函數

int process(char[] str, char[] t, int i, int j)

遞迴函數表示：str從i一直到最後，生成的序列可以匹配多少個t從j往後生成的字串

所以process(str,t,0,0)得到的結果就是答案。

接下來考慮遞迴函數的base case，

        if (j == t.length) {
            // 表示str已經把t整個都搞定了，返回1，說明得到了一種情況
            return 1;
        }
        // 到了這裡，說明t還沒到頭
        if (i == str.length) {
            // str已經沒有字串了，t又沒到頭，所以，無法匹配
            return 0;
        }

接下來是普遍位置，考慮str[i]是否參與匹配來決定下一步的操作，注：str[i]如果要參與匹配，則必須滿足str[i] == t[j]。

        // str[i]位置不參與匹配
        int ans = process(str, t, i + 1, j);
        if (str[i] == t[j]) {
            // str[i]參與，必須滿足str[i] == t[j]
            ans += process(str, t, i + 1, j + 1);
        }

完整程式碼如下

    public static int numDistinct(String s, String t) {
        if (s.length() < t.length()) {
            return 0;
        }
        return process(s.toCharArray(), t.toCharArray(), 0, 0);
    }

    // str[0....結尾]搞定t[0....結尾]
    public static int process(char[] str, char[] t, int i, int j) {
        if (j == t.length) {
            // 全部搞定了
            return 1;
        }
        if (i == str.length) {
            // 沒有了，搞不定
            return 0;
        }
        // 不用i位置的去搞定
        int ans = process(str, t, i + 1, j);
        if (str[i] == t[j]) {
            ans += process(str, t, i + 1, j + 1);
        }
        return ans;
    }

這個暴力解法在LeetCode上直接超時。

動態規劃

二維陣列

根據暴力方法，可以得到，遞迴函數只有兩個可變引數，所以定義二維dp，dp的含義和遞迴函數的含義保持一致。所以dp[0][0]就是答案。

        int m = str.length;
        int n = target.length;
        int[][] dp = new int[m + 1][n + 1];

根據暴力方法

        if (j == t.length) {
            // 全部搞定了
            return 1;
        }
        if (i == str.length) {
            // 沒有了，搞不定
            return 0;
        }

可以得到dp的最後一行都是1，即

        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = 1;
        }

接下來考慮普遍的dp[i][j]，根據暴力方法

        int ans = process(str, t, i + 1, j);
        if (str[i] == t[j]) {
            ans += process(str, t, i + 1, j + 1);
        }

可以得到，dp[i][j]依賴dp[i+1][j]和dp[i+1][j+1]（需要滿足str[i] == t[j]）位置的值。

所以

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + (str[i] == target[j] ? dp[i + 1][j + 1] : 0);
            }
        }

完整程式碼

    public static int numDistinct(String s, String t) {
        if (s.length() < t.length()) {
            return 0;
        }
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int m = str.length;
        int n = target.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + (str[i] == target[j] ? dp[i + 1][j + 1] : 0);
            }
        }
        return dp[0][0];
    }

時間複雜度O(m*n)，其中m和n分別是s和t的長度。

空間複雜度O(m*n)，其中m和n分別是s和t的長度。

一維陣列

通過分析上述動態規劃的解法，我們可得到一個結論，二維dp的計算順序是從最後一行到第一行，且當前行只依賴上一行有限幾個位置的資訊，所以，我們可以將上述二維表簡化成一維表，定義

        int m = str.length;
        int[] dp = new int[n + 1];

通過一維表的從最後一行到第一行的捲動更新，來得到第一行的值，完整程式碼如下

    public static int numDistinct(String s, String t) {
        if (s.length() < t.length()) {
            return 0;
        }
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int m = str.length;
        int n = target.length;
        int[] dp = new int[n + 1];
        dp[n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            // 這裡要注意，從左往右
            for (int j = 0; j <= n - 1; j++) {
                dp[j] += (str[i] == target[j] ? dp[j + 1] : 0);
            }

        }
        return dp[0];
    }

時間複雜度O(m*n)，其中m和n分別是s和t的長度。

空間複雜度O(n)，其中n是t的長度。

演演算法和資料結構筆記

不同的子序列問題I

不同的子序列問題I

題目連結

暴力解法

動態規劃

二維陣列

一維陣列

更多