您好,登錄后才能下訂單哦!
這篇文章主要介紹“C++怎么解決交織相錯(cuò)的字符串問(wèn)題”的相關(guān)知識(shí),小編通過(guò)實(shí)際案例向大家展示操作過(guò)程,操作方法簡(jiǎn)單快捷,實(shí)用性強(qiáng),希望這篇“C++怎么解決交織相錯(cuò)的字符串問(wèn)題”文章能幫助大家解決問(wèn)題。
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
這道求交織相錯(cuò)的字符串和之前那道 Word Break 的題很類(lèi)似,就像我之前說(shuō)的只要是遇到字符串的子序列或是匹配問(wèn)題直接就上動(dòng)態(tài)規(guī)劃 Dynamic Programming,其他的都不要考慮,什么遞歸呀的都是浮云(當(dāng)然帶記憶數(shù)組的遞歸寫(xiě)法除外,因?yàn)檫@也可以算是 DP 的一種),千辛萬(wàn)苦的寫(xiě)了遞歸結(jié)果拿到 OJ 上妥妥 Time Limit Exceeded,能把人氣昏了,所以還是直接就考慮 DP 解法省事些。一般來(lái)說(shuō)字符串匹配問(wèn)題都是更新一個(gè)二維 dp 數(shù)組,核心就在于找出狀態(tài)轉(zhuǎn)移方程。那么我們還是從題目中給的例子出發(fā)吧,手動(dòng)寫(xiě)出二維數(shù)組 dp 如下:
? d b b c a
? T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T
首先,這道題的大前提是字符串 s1 和 s2 的長(zhǎng)度和必須等于 s3 的長(zhǎng)度,如果不等于,肯定返回 false。那么當(dāng) s1 和 s2 是空串的時(shí)候,s3 必然是空串,則返回 true。所以直接給 dp[0][0] 賦值 true,然后若 s1 和 s2 其中的一個(gè)為空串的話,那么另一個(gè)肯定和 s3 的長(zhǎng)度相等,則按位比較,若相同且上一個(gè)位置為 True,賦 True,其余情況都賦 False,這樣的二維數(shù)組 dp 的邊緣就初始化好了。下面只需要找出狀態(tài)轉(zhuǎn)移方程來(lái)更新整個(gè)數(shù)組即可,我們發(fā)現(xiàn),在任意非邊緣位置 dp[i][j] 時(shí),它的左邊或上邊有可能為 True 或是 False,兩邊都可以更新過(guò)來(lái),只要有一條路通著,那么這個(gè)點(diǎn)就可以為 True。那么我們得分別來(lái)看,如果左邊的為 True,那么我們?nèi)コ?dāng)前對(duì)應(yīng)的 s2 中的字符串 s2[j - 1] 和 s3 中對(duì)應(yīng)的位置的字符相比(計(jì)算對(duì)應(yīng)位置時(shí)還要考慮已匹配的s1中的字符),為 s3[j - 1 + i], 如果相等,則賦 True,反之賦 False。 而上邊為 True 的情況也類(lèi)似,所以可以求出狀態(tài)轉(zhuǎn)移方程為:
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
其中 dp[i][j] 表示的是 s2 的前 i 個(gè)字符和 s1 的前 j 個(gè)字符是否匹配 s3 的前 i+j 個(gè)字符,根據(jù)以上分析,可寫(xiě)出代碼如下:
解法一:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; int n1 = s1.size(), n2 = s2.size(); vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1)); dp[0][0] = true; for (int i = 1; i <= n1; ++i) { dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); } for (int i = 1; i <= n2; ++i) { dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]); } for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]); } } return dp[n1][n2]; } };
我們也可以把for循環(huán)合并到一起,用if條件來(lái)處理邊界情況,整體思路和上面的解法沒(méi)有太大的區(qū)別,參見(jiàn)代碼如下:
解法二:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; int n1 = s1.size(), n2 = s2.size(); vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1, false)); for (int i = 0; i <= n1; ++i) { for (int j = 0; j <= n2; ++j) { if (i == 0 && j == 0) { dp[i][j] = true; } else if (i == 0) { dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]; } else if (j == 0) { dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]; } else { dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]); } } } return dp[n1][n2]; } };
這道題也可以使用帶優(yōu)化的 DFS 來(lái)做,我們使用一個(gè) HashSet,用來(lái)保存匹配失敗的情況,我們分別用變量i,j,和k來(lái)記錄字符串 s1,s2,和 s3 匹配到的位置,初始化的時(shí)候都傳入0。在遞歸函數(shù)中,首先根據(jù)i和j,算出 key 值,由于我們的 HashSet 中只能放一個(gè)數(shù)字,而我們要 encode 兩個(gè)數(shù)字i和j,所以通過(guò)用i乘以 s3 的長(zhǎng)度再加上j來(lái)得到 key,此時(shí)我們看,如果 key 已經(jīng)在集合中,直接返回 false,因?yàn)榧现写娴氖菬o(wú)法匹配的情況。然后先來(lái)處理 corner case 的情況,如果i等于 s1 的長(zhǎng)度了,說(shuō)明 s1 的字符都匹配完了,此時(shí) s2 剩下的字符和 s3 剩下的字符可以直接進(jìn)行匹配了,所以我們直接返回兩者是否能匹配的 bool 值。同理,如果j等于 s2 的長(zhǎng)度了,說(shuō)明 s2 的字符都匹配完了,此時(shí) s1 剩下的字符和 s3 剩下的字符可以直接進(jìn)行匹配了,所以我們直接返回兩者是否能匹配的 bool 值。如果 s1 和 s2 都有剩余字符,那么當(dāng) s1 的當(dāng)前字符等于 s3 的當(dāng)前字符,那么調(diào)用遞歸函數(shù),注意i和k都加上1,如果遞歸函數(shù)返回 true,則當(dāng)前函數(shù)也返回 true;還有一種情況是,當(dāng) s2 的當(dāng)前字符等于 s3 的當(dāng)前字符,那么調(diào)用遞歸函數(shù),注意j和k都加上1,如果遞歸函數(shù)返回 true,那么當(dāng)前函數(shù)也返回 true。如果匹配失敗了,則將 key 加入集合中,并返回 false 即可,參見(jiàn)代碼如下:
解法三:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; unordered_set<int> s; return helper(s1, 0, s2, 0, s3, 0, s); } bool helper(string& s1, int i, string& s2, int j, string& s3, int k, unordered_set<int>& s) { int key = i * s3.size() + j; if (s.count(key)) return false; if (i == s1.size()) return s2.substr(j) == s3.substr(k); if (j == s2.size()) return s1.substr(i) == s3.substr(k); if ((s1[i] == s3[k] && helper(s1, i + 1, s2, j, s3, k + 1, s)) || (s2[j] == s3[k] && helper(s1, i, s2, j + 1, s3, k + 1, s))) return true; s.insert(key); return false; } };
既然 DFS 可以,那么 BFS 也就坐不住了,也要出來(lái)浪一波。這里我們需要用隊(duì)列 queue 來(lái)輔助運(yùn)算,如果將解法一講解中的那個(gè)二維 dp 數(shù)組列出來(lái)的 TF 圖當(dāng)作一個(gè)迷宮的話,那么 BFS 的目的就是要從 (0, 0) 位置找一條都是T的路徑通到 (n1, n2) 位置,這里我們還要使用 HashSet,不過(guò)此時(shí)保存到是已經(jīng)遍歷過(guò)的位置,隊(duì)列中還是存 key 值,key 值的 encode 方法跟上面 DFS 解法的相同,初始時(shí)放個(gè)0進(jìn)去。然后我們進(jìn)行 while 循環(huán),循環(huán)條件除了q不為空,還有一個(gè)是k小于 n3,因?yàn)槠ヅ渫?s3 中所有的字符就結(jié)束了。然后由于是一層層的遍歷,所以要直接循環(huán) queue 中元素個(gè)數(shù)的次數(shù),在 for 循環(huán)中,對(duì)隊(duì)首元素進(jìn)行解碼,得到i和j值,如果i小于 n1,說(shuō)明 s1 還有剩余字符,如果 s1 當(dāng)前字符等于 s3 當(dāng)前字符,那么把 s1 的下一個(gè)位置 i+1 跟j一起加碼算出 key 值,如果該 key 值不在于集合中,則加入集合,同時(shí)加入隊(duì)列 queue 中;同理,如果j小于 n2,說(shuō)明 s2 還有剩余字符,如果 s2 當(dāng)前字符等于 s3 當(dāng)前字符,那么把 s2 的下一個(gè)位置 j+1 跟i一起加碼算出 key 值,如果該 key 值不在于集合中,則加入集合,同時(shí)加入隊(duì)列 queue 中。for 循環(huán)結(jié)束后,k自增1。最后如果匹配成功的話,那么 queue 中應(yīng)該只有一個(gè) (n1, n2) 的 key 值,且k此時(shí)等于 n3,所以當(dāng) queue 為空或者k不等于 n3 的時(shí)候都要返回 false,參見(jiàn)代碼如下:
解法四:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0; unordered_set<int> s; queue<int> q{{0}}; while (!q.empty() && k < n3) { int len = q.size(); for (int t = 0; t < len; ++t) { int i = q.front() / n3, j = q.front() % n3; q.pop(); if (i < n1 && s1[i] == s3[k]) { int key = (i + 1) * n3 + j; if (!s.count(key)) { s.insert(key); q.push(key); } } if (j < n2 && s2[j] == s3[k]) { int key = i * n3 + j + 1; if (!s.count(key)) { s.insert(key); q.push(key); } } } ++k; } return !q.empty() && k == n3; } };
關(guān)于“C++怎么解決交織相錯(cuò)的字符串問(wèn)題”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。