Java教程

不同的子序列问题I

本文主要是介绍不同的子序列问题I,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

不同的子序列问题I

作者:Grey

原文地址: 不同的子序列问题I

题目链接

LeetCode 115. 不同的子序列

暴力解法

定义递归函数

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

递归函数表示:stri一直到最后,生成的序列可以匹配多少个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上直接超时。

动态规划

二维数组

根据暴力方法,可以得到,递归函数只有两个可变参数,所以定义二维dpdp的含义和递归函数的含义保持一致。所以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),其中mn分别是st的长度。

空间复杂度O(m*n),其中mn分别是st的长度。

一维数组

通过分析上述动态规划的解法,我们可得到一个结论,二维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),其中mn分别是st的长度。

空间复杂度O(n),其中nt的长度。

更多

算法和数据结构笔记

这篇关于不同的子序列问题I的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!