資訊專欄INFORMATION COLUMN
摘要：計(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 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.
原題鏈接
動(dòng)態(tài)規(guī)劃法 復(fù)雜度時(shí)間 O(NM) 空間 O(NM)
思路這題的思路和EditDistance有些相似，我們需要一個(gè)二維數(shù)組dp(i)(j)來記錄長(zhǎng)度為i的字串在長(zhǎng)度為j的母串中出現(xiàn)的次數(shù)，這里長(zhǎng)度都是從頭算起的，而且遍歷時(shí)，保持子串長(zhǎng)度相同，先遞增母串長(zhǎng)度，母串最長(zhǎng)時(shí)再增加一點(diǎn)子串長(zhǎng)度重頭開始計(jì)算母串。
首先我們先要初始化矩陣，當(dāng)子串長(zhǎng)度為0時(shí)，所有次數(shù)都是1，當(dāng)母串長(zhǎng)度為0時(shí)，所有次數(shù)都是0.當(dāng)母串子串都是0長(zhǎng)度時(shí)，次數(shù)是1（因?yàn)槎际强?，相等）。接著，如果子串的最后一個(gè)字母和母串的最后一個(gè)字母不同，說明新加的母串字母沒有產(chǎn)生新的可能性，可以沿用該子串在較短母串的出現(xiàn)次數(shù)，所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一個(gè)字母和母串的最后一個(gè)字母相同，說明新加的母串字母帶來了新的可能性，我們不僅算上dp(i)(j-1)，也要算上新的可能性。那么如何計(jì)算新的可能性呢，其實(shí)就是在既沒有最后這個(gè)母串字母也沒有最后這個(gè)子串字母時(shí)，子串出現(xiàn)的次數(shù)，我們相當(dāng)于為所有這些可能性都添加一個(gè)新的可能。所以，這時(shí)dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下圖是以rabbbit和rabbit為例的矩陣示意圖。計(jì)算元素值時(shí)，當(dāng)末尾字母一樣，實(shí)際上是左方數(shù)字加左上方數(shù)字，當(dāng)不一樣時(shí)，就是左方的數(shù)字。
示意圖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：如果這個(gè)字符串有1000000個(gè)char怎么辦？
A：用暴力法，對(duì)每一位開始向后檢查是否是subsequence。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66165.html
摘要：用動(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...
摘要：題目要求判斷字符串中通過刪減單詞含有幾個(gè)字符串。例如中含有個(gè)字符串，通過分別刪除第，，個(gè)。也就是說，我們需要通過一個(gè)數(shù)據(jù)結(jié)構(gòu)來記錄臨時(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 equa...
摘要：截取和出來填表。這里沒有新路徑產(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...
摘要：終于見到一個(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...
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: ...
閱讀 3143·2021-11-11 16:54
閱讀 2321·2021-09-04 16:48
閱讀 3228·2019-08-29 16:08
閱讀 649·2019-08-29 15:13
閱讀 1354·2019-08-29 15:09
閱讀 2671·2019-08-29 12:45
閱讀 1936·2019-08-29 12:12
閱讀 459·2019-08-26 18:27
