###題目

給定一個字符串 s1，我們可以把它遞歸地分割成兩個非空子字符串，從而將其表示為二叉樹，下圖是字符串 s1="great"的一種可能的表示形式。

在擾亂這個字符串的過程中，我們可以挑選任何一個非葉節(jié)點(diǎn)，然后交換它的兩個子節(jié)點(diǎn)。例如，如果我們挑選非葉節(jié)點(diǎn) "gr" ，交換它的兩個子節(jié)點(diǎn)，將會產(chǎn)生擾亂字符串 "rgeat" 。

我們將 "rgeat” 稱作 "great" 的一個擾亂字符串。同樣地，如果我們繼續(xù)交換節(jié)點(diǎn) "eat" 和 "at" 的子節(jié)點(diǎn)，將會產(chǎn)生另一個新的擾亂字符串 "rgtae" 。

我們將 "rgtae” 稱作 "great" 的一個擾亂字符串。給出兩個長度相等的字符串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字符串。

• 輸入: s1 = "great", s2 = "rgeat"
• 輸出: true
• 輸入: s1 = "abcde", s2 = "caebd"
• 輸出: false

###思路

這樣來進(jìn)行理解，給定的兩個字符串s1和s2，若如果s1和s2長度不一樣，那么兩者不為擾動字符串，如果長度一樣，在進(jìn)行判斷，首先字符串s1能夠劃分為s1_1、s1_2 。同理那么，s2可以劃分成s2_1、s2_2，現(xiàn)在出現(xiàn)了兩種情況：

• 沒發(fā)生擾動，那么s1_1=s2_1、s1_2=s2_2。
• 發(fā)生了擾動，那么s1_1=s2_2、s1_2=s2_1.

那么只要兩個字符串分割而成的子字符串之間滿足上面兩種情況中的任意一種，那么就可以認(rèn)為它們兩是擾動字符串，4個互為擾動字符串的字符串合并而來的兩個字符串肯定也是互為擾動字符串。

我們建立dp矩陣，

表示從s1的i開始的長度為l的字符串是否和s2的j開始的長度為l的字符串互為擾動字符串。

轉(zhuǎn)移方程為

前后兩個分別代表了兩種情況，滿足其一就可以了。

初始情況為長度是1的子串，此時只有相等才能變過去，所以相等為true，不相等為false。

###code

class

###思路

看到別人修改成了遞歸版本，看起來舒服多了，也容易理解。

###代碼

class

總結(jié)

以上是生活随笔為你收集整理的jsp判断字符串相等_leetcode 86 扰乱字符串(c++)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。