国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

dailybird / 1853人閱讀

摘要：用動規(guī)方法做建立長度為和的二維數(shù)組，表示的第到位子串包含不同的的第到位子串的個數(shù)。初始化當(dāng)?shù)淖哟L度為時，當(dāng)?shù)淖哟L度為時，當(dāng)和子串都為時，包含，故。

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

用動規(guī)方法做：
建立長度為m+1和n+1的二維dp數(shù)組，dp[i][j]表示S的第0到i位子串包含不同的T的第0到j(luò)位子串的個數(shù)。
初始化：當(dāng)T的子串長度為0時，dp[i][0] = 1；當(dāng)S的子串長度為0時，dp[0][i] = 0；當(dāng)S和T子串都為0時，0包含0，故dp[0][0] = 1。
兩次循環(huán)S和T，若S的最后一位和T的最后一位不同，那么S增加一位不會增加更多的包含關(guān)系，即dp[i][j]仍然等于dp[i-1][j]。若S的最后一位和T的最后一位相等，最后的結(jié)果一定也包含S和T各減一位的結(jié)果，如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];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/65796.html

相關(guān)文章

  • [Leetcode] Distinct Subsequences 不同順序字串

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

    SnaiLiu 評論0 收藏0

  • [LintCode/LeetCode] Unique Paths

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

    Gu_Yan 評論0 收藏0

  • [LintCode/LeetCode] Unique Paths II

    摘要：和完全一樣的做法，只要在初始化首行和首列遇到時置零且即可。對了，數(shù)組其它元素遇到也要置零喏，不過就不要啦。 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 評論0 收藏0

  • leetcode115. Distinct Subsequences

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

    NSFish 評論0 收藏0

  • Distinct Subsequences

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

    Ajian 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<