成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode115. Distinct Subsequences

NSFish / 3091人閱讀

摘要：題目要求判斷字符串中通過(guò)刪減單詞含有幾個(gè)字符串。例如中含有個(gè)字符串，通過(guò)分別刪除第，，個(gè)。也就是說(shuō)，我們需要通過(guò)一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄臨時(shí)結(jié)果從而支持我們?cè)谝阎懊鎺讉€(gè)情況的場(chǎng)景下對(duì)后續(xù)情況進(jìn)行計(jì)算。

題目要求 
Given a string S and a string T, count the number of distinct subsequences of S which equals T.

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).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

判斷S字符串中通過(guò)刪減單詞含有幾個(gè)T字符串。例如rabbbit中含有3個(gè)rabbit字符串，通過(guò)分別刪除第1，2，3個(gè)b。

思路和代碼

這時(shí)一道典型的DP題。也就是說(shuō)，我們需要通過(guò)一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄臨時(shí)結(jié)果從而支持我們?cè)谝阎懊鎺讉€(gè)情況的場(chǎng)景下對(duì)后續(xù)情況進(jìn)行計(jì)算。在這道題目中，如果我們想要計(jì)算S中含有幾個(gè)T（假設(shè)S長(zhǎng)度為n，T長(zhǎng)度為m），那么我們只需要知道S[0...n]含有幾個(gè)T[0...m-1]以及S[0...n-1]含有幾個(gè)T[0...m-1]。
從中歸納出最普遍的場(chǎng)景，也就是如果想要計(jì)算S[0...i]含有幾個(gè)T[0...j]，可以從以下兩種場(chǎng)景來(lái)考慮：

1.S[i]!=T[j]
那么S[0...i]包含的T[0...j]的數(shù)量等價(jià)于S[0...i-1]包含T[0...j]的數(shù)量。
2.S[i]==T[j]
那么S[0...i]包含的T[0...j]的數(shù)量等價(jià)于S[0...i-1]包含T[0...j]的數(shù)量**加上**S[0...i-1]包含T[0...j-1]的數(shù)量

再來(lái)考慮初始的極端情況

1.j==0，此時(shí)S為一個(gè)空字符串，那么S的任何自字符串都包含一個(gè)唯一空字符串
2.i==0&&j！=0 此時(shí)S為非空字符串而T為空字符串，那么S包含0個(gè)T

之后我們采用intm+1來(lái)存儲(chǔ)臨時(shí)變量，其中inti+1表示S[0...j]含有幾個(gè)T[0...i]
代碼如下：

    public int numDistinct(String s, String t) {
        if(s==null || t==null) return 0;
        if(t.isEmpty()) return 1;
        int[][] temp = new int[t.length()+1][s.length()+1];
        for(int i = 0 ; i

對(duì)這段代碼的優(yōu)化我們可以考慮不采用二維數(shù)組而采用一維數(shù)組的方式來(lái)存儲(chǔ)過(guò)程值：


    public int numDistinct2(String s, String t) {
        int[] array = new int[s.length()+1];
        int prev = 1;
        for(int i = 0 ; i


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70346.html

相關(guān)文章

  • 115 Distinct Subsequences

    摘要：截取和出來(lái)填表。這里沒(méi)有新路徑產(chǎn)生，就是最大可能的值。 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 str...

    LittleLiByte 評(píng)論0 收藏0

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

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

    SnaiLiu 評(píng)論0 收藏0

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

    摘要：用動(dòng)規(guī)方法做建立長(zhǎng)度為和的二維數(shù)組，表示的第到位子串包含不同的的第到位子串的個(gè)數(shù)。初始化當(dāng)?shù)淖哟L(zhǎng)度為時(shí)，當(dāng)?shù)淖哟L(zhǎng)度為時(shí)，當(dāng)和子串都為時(shí)，包含，故。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a strin...

    dailybird 評(píng)論0 收藏0

  • Distinct Subsequences

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

    Ajian 評(píng)論0 收藏0

  • [LeetCode] 491. Increasing Subsequences

    Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: ...

    wupengyu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<