如何求一個字符串中有多少個pat

本篇內(nèi)容介紹了“如何求一個字符串中有多少個pat”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

在婁煩等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務理念，為客戶提供成都網(wǎng)站設(shè)計、成都網(wǎng)站制作 網(wǎng)站設(shè)計制作按需網(wǎng)站開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站建設(shè),網(wǎng)絡(luò)營銷推廣,外貿(mào)網(wǎng)站建設(shè),婁煩網(wǎng)站建設(shè)費用合理。

有幾個pat

這是pat的一道題。

分析

如何求一個字符串中有多少個pat。不要想著三重for循環(huán)去枚舉所有情況了，那不是好的方法。這這種題如果有靈感的話應該能猜出來這應該是一種動態(tài)規(guī)劃的問題。

首先將問題簡單分解一下，如果問原串中有多少個p。那么很容易枚舉一遍即可。例如序列ppp就是三個p。

如果帶上a，求串pa的個數(shù)呢?pa是由p和a組成。求pa的個數(shù)肯定和a有很大的關(guān)系，每個a可能會組成若干個pa取決于這個a前面p的數(shù)量。將所有a位置組成的pa相加即可。例如pppapa  總共可以組合3+4=7個pa.

同理想知道有幾個pat那也很容易啊，pat的求解需要找到每個t，然后知道當前位置前面有多少個pa，疊加求解獲得結(jié)果即可。結(jié)合下圖流程看更好。

不同的子序列

題目描述：

給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現(xiàn)的個數(shù)。

字符串的一個 子序列 是指，通過刪除一些(也可以不刪除)字符且不干擾剩余字符相對位置所組成的新字符串。(例如，"ACE" 是 "ABCDE"  的一個子序列，而 "AEC" 不是)

題目數(shù)據(jù)保證答案符合 32 位帶符號整數(shù)范圍。

示例 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串的長度不固定，所以處理上就要使用數(shù)組來處理而不能直接if  else。

這題的思路肯定也是動態(tài)規(guī)劃dp了，dp[j]的意思就是t串中[0,j-1]長字符在s中能夠匹配的數(shù)量(當然這個值從前往后是動態(tài)變化的)，數(shù)組大小為dp[t.length+1]。在遍歷s串的每一個元素都要和t串中所有元素進行對比看看是否相等，如果s串枚舉到的這個串和t串中的第j個相等。那么dp[j+1]+=dp[j]。你可能會問為啥是dp[j+1],因為第一個元素匹配到需要將數(shù)量+1，而這里為了避免(判斷是否為首字符)這樣的判斷我們將dp[0]=1,這樣t串的每個元素都能正常的操作。

但是有一點需要注意的就是在遍歷s串中第i個字母的時候，遍歷t串比較不能從左向右而必須從右向左。因為在遍歷s串的第i個字符在枚舉dp數(shù)組時候要求此刻數(shù)據(jù)是相對靜止的疊加(即同一層次不能產(chǎn)生影響)，而從左往右進行遇到相同字符會對后面的值產(chǎn)生影響。區(qū)別的話可以參考下圖這個例子：

實現(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];     } }

“如何求一個字符串中有多少個pat”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

網(wǎng)站欄目：如何求一個字符串中有多少個pat
鏈接分享：http://muchs.cn/article40/jpesho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計公司、Google、網(wǎng)站導航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)