Different subsequence problems I

author ：Grey

Original address : Different subsequence problems I

Topic link

LeetCode 115. Different subsequences

Violence solution

Define recursive functions

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

Recursive functions represent ：str from i All the way to the end , How many can the generated sequence match t from j The string generated later

therefore process(str,t,0,0) The result is the answer .

Next, consider the... Of recursive functions base case,

        if (j == t.length) {
    
            //  Express str Have the t The whole thing is done , return 1, It shows that there is a situation 
            return 1;
        }
        //  Here we are. , explain t It's not over yet 
        if (i == str.length) {
    
            // str There are no strings anymore ,t It's not the end , therefore , Can't match 
            return 0;
        }

Next up is the universal location , consider str[i] Whether to participate in matching determines the next operation , notes ：str[i] If you want to participate in matching , Then we must satisfy str[i] == t[j].

        // str[i] Position does not participate in matching 
        int ans = process(str, t, i + 1, j);
        if (str[i] == t[j]) {
    
            // str[i] Participate in , Must satisfy str[i] == t[j]
            ans += process(str, t, i + 1, j + 1);
        }

The complete code is as follows

    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.... ending ] Get it done t[0.... ending ]
    public static int process(char[] str, char[] t, int i, int j) {
    
        if (j == t.length) {
    
            //  It's all done 
            return 1;
        }
        if (i == str.length) {
    
            //  period , Uncertain 
            return 0;
        }
        //  no need i The position should be fixed 
        int ans = process(str, t, i + 1, j);
        if (str[i] == t[j]) {
    
            ans += process(str, t, i + 1, j + 1);
        }
        return ans;
    }

This violent solution is LeetCode Upper direct timeout .

Dynamic programming

Two dimensional array

According to the method of violence , You can get , A recursive function has only two mutable arguments , So define two dimensions dp,dp The meaning of is consistent with that of recursive function . therefore dp[0][0] That's the answer. .

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

According to the method of violence

        if (j == t.length) {
    
            //  It's all done 
            return 1;
        }
        if (i == str.length) {
    
            //  period , Uncertain 
            return 0;
        }

You can get dp The last line of is 1, namely

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

Next consider the general dp[i][j], According to the method of violence

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

You can get ,dp[i][j] rely on dp[i+1][j] and dp[i+1][j+1]（ Need to meet str[i] == t[j]） The value of the location .

therefore

        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);
            }
        }

Complete code

    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];
    }

Time complexity O(m*n), among m and n Namely s and t The length of .

Spatial complexity O(m*n), among m and n Namely s and t The length of .

One dimensional array

By analyzing the solution of the above dynamic programming , We can draw a conclusion , A two-dimensional dp The order of calculation is From the last line to the first line , And the current row only depends on the information of a limited number of positions in the previous row , therefore , We can simplify the above two-dimensional table into one-dimensional table , Definition

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

Through the rolling update from the last row to the first row of the one-dimensional table , To get the value of the first row , The complete code is as follows

    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--) {
    
            //  Pay attention here , From left to right 
            for (int j = 0; j <= n - 1; j++) {
    
                dp[j] += (str[i] == target[j] ? dp[j + 1] : 0);
            }

        }
        return dp[0];
    }

Time complexity O(m*n), among m and n Namely s and t The length of .

Spatial complexity O(n), among n yes t The length of .

more

Algorithm and data structure notes