leetcode115. Distinct Subsequences

NSFish 發布于2019-08-16 10:44 / 3028人閱讀

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

題目要求

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字符串中通過刪減單詞含有幾個T字符串。例如rabbbit中含有3個rabbit字符串，通過分別刪除第1，2，3個b。

思路和代碼

這時一道典型的DP題。也就是說，我們需要通過一個數據結構來記錄臨時結果從而支持我們在已知前面幾個情況的場景下對后續情況進行計算。在這道題目中，如果我們想要計算S中含有幾個T（假設S長度為n，T長度為m），那么我們只需要知道S[0...n]含有幾個T[0...m-1]以及S[0...n-1]含有幾個T[0...m-1]。
從中歸納出最普遍的場景，也就是如果想要計算S[0...i]含有幾個T[0...j]，可以從以下兩種場景來考慮：

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

再來考慮初始的極端情況

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

之后我們采用intm+1來存儲臨時變量，其中inti+1表示S[0...j]含有幾個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
對這段代碼的優化我們可以考慮不采用二維數組而采用一維數組的方式來存儲過程值：
    public int numDistinct2(String s, String t) {
        int[] array = new int[s.length()+1];
        int prev = 1;
        for(int i = 0 ; i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Subsequences Leetcod LeetCode Distinct

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

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

115 Distinct Subsequences

摘要：截取和出來填表。這里沒有新路徑產生，就是最大可能的值。 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 2019-08-14 17:59 評論0 收藏0
[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] Distinct Subsequences [一維DP]

摘要：用動規方法做建立長度為和的二維數組，表示的第到位子串包含不同的的第到位子串的個數。初始化當的子串長度為時，當的子串長度為時，當和子串都為時，包含，故。 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 2019-08-14 15:29 評論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
[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 2019-08-16 13:50 評論0 收藏0