[Leetcode] Distinct Subsequences 不同順序字串

SnaiLiu 發布于2019-08-14 16:11 / 2676人閱讀

摘要：計算元素值時，當末尾字母一樣，實際上是左方數字加左上方數字，當不一樣時，就是左方的數字。示意圖代碼如果這個字符串有個怎么辦用暴力法，對每一位開始向后檢查是否是。

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

原題鏈接

動態規劃法 復雜度

時間 O(NM) 空間 O(NM)

思路

這題的思路和EditDistance有些相似，我們需要一個二維數組dp(i)(j)來記錄長度為i的字串在長度為j的母串中出現的次數，這里長度都是從頭算起的，而且遍歷時，保持子串長度相同，先遞增母串長度，母串最長時再增加一點子串長度重頭開始計算母串。

首先我們先要初始化矩陣，當子串長度為0時，所有次數都是1，當母串長度為0時，所有次數都是0.當母串子串都是0長度時，次數是1（因為都是空，相等）。接著，如果子串的最后一個字母和母串的最后一個字母不同，說明新加的母串字母沒有產生新的可能性，可以沿用該子串在較短母串的出現次數，所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一個字母和母串的最后一個字母相同，說明新加的母串字母帶來了新的可能性，我們不僅算上dp(i)(j-1)，也要算上新的可能性。那么如何計算新的可能性呢，其實就是在既沒有最后這個母串字母也沒有最后這個子串字母時，子串出現的次數，我們相當于為所有這些可能性都添加一個新的可能。所以，這時dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下圖是以rabbbit和rabbit為例的矩陣示意圖。計算元素值時，當末尾字母一樣，實際上是左方數字加左上方數字，當不一樣時，就是左方的數字。

示意圖

     0    r    a    b    b    b    i    t
0    1    1    1    1    1    1    1    1
r    0    1    1    1    1    1    1    1
a    0    0    1    1    1    1    1    1
b    0    0    0    1    2    3    3    3
b    0    0    0    0    1    3    3    3
i    0    0    0    0    0    0    3    3
t    0    0    0    0    0    0    0    3

代碼

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

Follow Up

Q：如果這個字符串有1000000個char怎么辦？
A：用暴力法，對每一位開始向后檢查是否是subsequence。

GPU云服務器云服務器不同順序排列 Subsequences LeetCode LeetCode_String

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

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

[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
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
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
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