面試官給我個字符串問里面有多少個"bigsai"子序列給我難住了
本文轉載自微信公眾號「bigsai」，作者bigsai。轉載本文請聯系bigsai公眾號。
前言
一次面試官笑嘻嘻的問我一個問題，場景還原一下：
然后我把這個問題透徹的研究了一下，并由淺入深的分析了一下這種問題的思路，分別是有幾個pat和不同子序列問題。
有幾個pat
這是pat的一道題。
分析
如何求一個字符串中有多少個pat。不要想著三重for循環去枚舉所有情況了，那不是好的方法。這這種題如果有靈感的話應該能猜出來這應該是一種動態規劃的問題。
首先將問題簡單分解一下，如果問原串中有多少個p。那么很容易枚舉一遍即可。例如序列ppp就是三個p。
如果帶上a，求串pa的個數呢?pa是由p和a組成。求pa的個數肯定和a有很大的關系，每個a可能會組成若干個pa取決于這個a前面p的數量。將所有a位置組成的pa相加即可。例如pppapa 總共可以組合3+4=7個pa.
同理想知道有幾個pat那也很容易啊，pat的求解需要找到每個t，然后知道當前位置前面有多少個pa，疊加求解獲得結果即可。結合下圖流程看更好。
不同的子序列
題目描述：
給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現的個數。
字符串的一個 子序列 是指，通過刪除一些(也可以不刪除)字符且不干擾剩余字符相對位置所組成的新字符串。(例如，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是)
題目數據保證答案符合 32 位帶符號整數范圍。
示例 1：
- 輸入：s = "rabbbit", t = "rabbit"
- 輸出：3
- 解釋：
- 如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。
- (上箭頭符號 ^ 表示選取的字母)
- rabbbit
- ^^^^ ^^
- rabbbit
- ^^ ^^^^
- rabbbit
- ^^^ ^^^
示例 2：
- 輸入：s = "babgbag", t = "bag"
- 輸出：5
- 解釋：
- 如下圖所示, 有 5 種可以從 s 中得到 "bag" 的方案。
- (上箭頭符號 ^ 表示選取的字母)
- babgbag
- ^^ ^
- babgbag
- ^^ ^
- babgbag
- ^ ^^
- babgbag
- ^ ^^
- babgbag
- ^^^
提示：
- 0 <= s.length, t.length <= 1000
- s 和 t 由英文字母組成
分析：
這個問題其實就是上面有幾個pat的變形拓展，其基本思想其實是一致的，上面那題問的是有幾個pat，固定、且很短。但這里面t串的長度不固定，所以處理上就要使用數組來處理而不能直接if else。
這題的思路肯定也是動態規劃dp了，dp[j]的意思就是t串中[0,j-1]長字符在s中能夠匹配的數量(當然這個值從前往后是動態變化的)，數組大小為dp[t.length+1]。在遍歷s串的每一個元素都要和t串中所有元素進行對比看看是否相等，如果s串枚舉到的這個串和t串中的第j個相等。那么dp[j+1]+=dp[j]。你可能會問為啥是dp[j+1],因為第一個元素匹配到需要將數量+1，而這里為了避免(判斷是否為首字符)這樣的判斷我們將dp[0]=1,這樣t串的每個元素都能正常的操作。
但是有一點需要注意的就是在遍歷s串中第i個字母的時候，遍歷t串比較不能從左向右而必須從右向左。因為在遍歷s串的第i個字符在枚舉dp數組時候要求此刻數據是相對靜止的疊加(即同一層次不能產生影響)，而從左往右進行遇到相同字符會對后面的值產生影響。區別的話可以參考下圖這個例子：
實現的代碼為：
- class Solution {
- public int numDistinct(String s, String t) {
- char s1[]=s.toCharArray();
- char t1[]=t.toCharArray();
- int dp[]=new int[t1.length+1];
- dp[0]=1;//用來疊加
- for(int i=0;i<s1.length;i++)
- {
- for(int j=t1.length-1;j>=0;j--)
- {
- if(t1[j]==s1[i])
- {
- dp[j+1]+=dp[j];
- }
- }
- }
- return dp[t1.length];
- }
- }
原文鏈接：https://mp.weixin.qq.com/s/Q60QEOTs_5hC4-hIuP4TjA
