[LintCode/LeetCode] Distinct Subsequences [一維DP]

dailybird 發布于2019-08-14 15:29 / 1861人閱讀

摘要：用動規方法做建立長度為和的二維數組，表示的第到位子串包含不同的的第到位子串的個數。初始化當的子串長度為時，當的子串長度為時，當和子串都為時，包含，故。

Problem

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Note

用動規方法做：
建立長度為m+1和n+1的二維dp數組，dp[i][j]表示S的第0到i位子串包含不同的T的第0到j位子串的個數。
初始化：當T的子串長度為0時，dp[i][0] = 1；當S的子串長度為0時，dp[0][i] = 0；當S和T子串都為0時，0包含0，故dp[0][0] = 1。
兩次循環S和T，若S的最后一位和T的最后一位不同，那么S增加一位不會增加更多的包含關系，即dp[i][j]仍然等于dp[i-1][j]。若S的最后一位和T的最后一位相等，最后的結果一定也包含S和T各減一位的結果，如S="abb"，T="ab"，所以dp[i][j]包含dp[i-1][j-1]，再與與dp[i-1][j]相加。

見下面的例子。

     0    A    B    C

0    1    0    0    0

C    1    0    0    0
    
A    1    1    0    0  

B    1    1    1    0   

B    1    1    2    0
 
B    1    1    3    0

C    1    1    3    3

Solution

public class Solution {
    public int numDistinct(String S, String T) {
        int m = S.length(), n = T.length();
        if (m < n) return 0;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) dp[i][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (S.charAt(i-1) == T.charAt(j-1)) dp[i][j] += dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

One-dimension DP, O(n) space

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {                   
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[j] += dp[j-1];
                }
            }
        }
        return dp[n];
    }
}

云服務器 GPU云服務器 Subsequences Distinct distinct去重 sql中distinct

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65796.html

[Leetcode] Distinct Subsequences 不同順序字串

摘要：計算元素值時，當末尾字母一樣，實際上是左方數字加左上方數字，當不一樣時，就是左方的數字。示意圖代碼如果這個字符串有個怎么辦用暴力法，對每一位開始向后檢查是否是。 Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of T in S. A su...

SnaiLiu 2019-08-14 16:11 評論0 收藏0
[LintCode/LeetCode] Unique Paths

摘要：簡單的動規題目，建立數組。坐標為矩陣的坐標，值為從左上角到這一格的走法總數。賦初值，最上一行和最左列的所有格子的走法都只有一種，其余格子的走法等于其左邊格子走法與上方格子走法之和。最后，返回即可。 Problem A robot is located at the top-left corner of a m x n grid (marked Start in the diagram ...

Gu_Yan 2019-08-14 15:27 評論0 收藏0
[LintCode/LeetCode] Unique Paths II

摘要：和完全一樣的做法，只要在初始化首行和首列遇到時置零且即可。對了，數組其它元素遇到也要置零喏，不過就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 評論0 收藏0
leetcode115. Distinct Subsequences

摘要：題目要求判斷字符串中通過刪減單詞含有幾個字符串。例如中含有個字符串，通過分別刪除第，，個。也就是說，我們需要通過一個數據結構來記錄臨時結果從而支持我們在已知前面幾個情況的場景下對后續情況進行計算。題目要求 Given a string S and a string T, count the number of distinct subsequences of S which equa...

NSFish 2019-08-16 10:44 評論0 收藏0
Distinct Subsequences

摘要：終于見到一個使用動態規劃的題目了，似乎這種字符串比對的差不多都是的思路。從后向前遞推，我們可以得到下面的矩陣可以看出，矩陣中每個的數值為，這樣右下角的值即為所求。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of...

Ajian 2019-07-24 17:32 評論0 收藏0