您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“如何求一個(gè)字符串中有多少個(gè)pat”的有關(guān)知識(shí),在實(shí)際案例的操作過程中,不少人都會(huì)遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
有幾個(gè)pat
這是pat的一道題。
分析
如何求一個(gè)字符串中有多少個(gè)pat。不要想著三重for循環(huán)去枚舉所有情況了,那不是好的方法。這這種題如果有靈感的話應(yīng)該能猜出來這應(yīng)該是一種動(dòng)態(tài)規(guī)劃的問題。
首先將問題簡單分解一下,如果問原串中有多少個(gè)p。那么很容易枚舉一遍即可。例如序列ppp就是三個(gè)p。
如果帶上a,求串pa的個(gè)數(shù)呢?pa是由p和a組成。求pa的個(gè)數(shù)肯定和a有很大的關(guān)系,每個(gè)a可能會(huì)組成若干個(gè)pa取決于這個(gè)a前面p的數(shù)量。將所有a位置組成的pa相加即可。例如pppapa 總共可以組合3+4=7個(gè)pa.
同理想知道有幾個(gè)pat那也很容易啊,pat的求解需要找到每個(gè)t,然后知道當(dāng)前位置前面有多少個(gè)pa,疊加求解獲得結(jié)果即可。結(jié)合下圖流程看更好。
不同的子序列
題目描述:
給定一個(gè)字符串 s 和一個(gè)字符串 t ,計(jì)算在 s 的子序列中 t 出現(xiàn)的個(gè)數(shù)。
字符串的一個(gè) 子序列 是指,通過刪除一些(也可以不刪除)字符且不干擾剩余字符相對(duì)位置所組成的新字符串。(例如,"ACE" 是 "ABCDE" 的一個(gè)子序列,而 "AEC" 不是)
題目數(shù)據(jù)保證答案符合 32 位帶符號(hào)整數(shù)范圍。
示例 1:
輸入:s = "rabbbit", t = "rabbit" 輸出:3 解釋: 如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。 (上箭頭符號(hào) ^ 表示選取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^
示例 2:
輸入:s = "babgbag", t = "bag" 輸出:5 解釋: 如下圖所示, 有 5 種可以從 s 中得到 "bag" 的方案。 (上箭頭符號(hào) ^ 表示選取的字母) babgbag ^^ ^ babgbag ^^ ^ babgbag ^ ^^ babgbag ^ ^^ babgbag ^^^
提示:
0 <= s.length, t.length <= 1000 s 和 t 由英文字母組成
分析:
這個(gè)問題其實(shí)就是上面有幾個(gè)pat的變形拓展,其基本思想其實(shí)是一致的,上面那題問的是有幾個(gè)pat,固定、且很短。但這里面t串的長度不固定,所以處理上就要使用數(shù)組來處理而不能直接if else。
這題的思路肯定也是動(dòng)態(tài)規(guī)劃dp了,dp[j]的意思就是t串中[0,j-1]長字符在s中能夠匹配的數(shù)量(當(dāng)然這個(gè)值從前往后是動(dòng)態(tài)變化的),數(shù)組大小為dp[t.length+1]。在遍歷s串的每一個(gè)元素都要和t串中所有元素進(jìn)行對(duì)比看看是否相等,如果s串枚舉到的這個(gè)串和t串中的第j個(gè)相等。那么dp[j+1]+=dp[j]。你可能會(huì)問為啥是dp[j+1],因?yàn)榈谝粋€(gè)元素匹配到需要將數(shù)量+1,而這里為了避免(判斷是否為首字符)這樣的判斷我們將dp[0]=1,這樣t串的每個(gè)元素都能正常的操作。
但是有一點(diǎn)需要注意的就是在遍歷s串中第i個(gè)字母的時(shí)候,遍歷t串比較不能從左向右而必須從右向左。因?yàn)樵诒闅vs串的第i個(gè)字符在枚舉dp數(shù)組時(shí)候要求此刻數(shù)據(jù)是相對(duì)靜止的疊加(即同一層次不能產(chǎn)生影響),而從左往右進(jìn)行遇到相同字符會(huì)對(duì)后面的值產(chǎn)生影響。區(qū)別的話可以參考下圖這個(gè)例子:
實(shí)現(xiàn)的代碼為:
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]; } }
“如何求一個(gè)字符串中有多少個(gè)pat”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。