使用下面描述的演算法可以擾亂字串 s 得到字串 t ：
如果字串的長度為 1 ，演算法停止
如果字串的長度 > 1 ，執行下述步驟：
在一個隨機下標處將字串分割成兩個非空的子字串，即，如果已知字串 s ，則可以將其分成兩個子字串 x 和 y ，且滿足 s = x + y ，
隨機 決定是要「交換兩個子字串」還是要「保持這兩個子字串的順序不變」，即，在執行這一步驟之后，s 可能是 s = x + y 或者 s = y + x ，
在 x 和 y 這兩個子字串上繼續從步驟 1 開始遞回執行此演算法，
給你兩個 長度相等 的字串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字串，如果是，回傳 true ；否則，回傳 false ，
示例 1：
輸入：s1 = “great”, s2 = “rgeat”
輸出：true
解釋：s1 上可能發生的一種情形是：
“great” --> “gr/eat” // 在一個隨機下標處分割得到兩個子字串
“gr/eat” --> “gr/eat” // 隨機決定：「保持這兩個子字串的順序不變」
“gr/eat” --> “g/r / e/at” // 在子字串上遞回執行此演算法，兩個子字串分別在隨機下標處進行一輪分割
“g/r / e/at” --> “r/g / e/at” // 隨機決定：第一組「交換兩個子字串」，第二組「保持這兩個子字串的順序不變」
“r/g / e/at” --> “r/g / e/ a/t” // 繼續遞回執行此演算法，將 “at” 分割得到 “a/t”
“r/g / e/ a/t” --> “r/g / e/ a/t” // 隨機決定：「保持這兩個子字串的順序不變」
演算法終止，結果字串和 s2 相同，都是 “rgeat”
這是一種能夠擾亂 s1 得到 s2 的情形，可以認為 s2 是 s1 的擾亂字串，回傳 true
示例 2：
輸入：s1 = “abcde”, s2 = “caebd”
輸出：false
示例 3：
輸入：s1 = “a”, s2 = “a”
輸出：true
提示：
s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小寫英文字母組成
解題思路：
這是一道很有難度的動態規劃題目，代碼的步驟很復雜，建議參考題解弄清楚，代碼如下：
class Solution {
private:
// 記憶化搜索存盤狀態的陣列
// -1 表示 false，1 表示 true，0 表示未計算
int memo[30][30][31];
string s1, s2;
public:
bool checkIfSimilar(int i1, int i2, int length) {
unordered_map<int, int> freq;
for (int i = i1; i < i1 + length; ++i) {
++freq[s1[i]];
}
for (int i = i2; i < i2 + length; ++i) {
--freq[s2[i]];
}
if (any_of(freq.begin(), freq.end(), [](const auto& entry) {return entry.second != 0;})) {
return false;
}
return true;
}
// 第一個字串從 i1 開始，第二個字串從 i2 開始，子串的長度為 length，是否和諧
bool dfs(int i1, int i2, int length) {
if (memo[i1][i2][length]) {
return memo[i1][i2][length] == 1;
}
// 判斷兩個子串是否相等
if (s1.substr(i1, length) == s2.substr(i2, length)) {
memo[i1][i2][length] = 1;
return true;
}
// 判斷是否存在字符 c 在兩個子串中出現的次數不同
if (!checkIfSimilar(i1, i2, length)) {
memo[i1][i2][length] = -1;
return false;
}
// 列舉分割位置
for (int i = 1; i < length; ++i) {
// 不交換的情況
if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
// 交換的情況
if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
}
memo[i1][i2][length] = -1;
return false;
}
bool isScramble(string s1, string s2) {
memset(memo, 0, sizeof(memo));
this->s1 = s1;
this->s2 = s2;
return dfs(0, 0, s1.size());
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277142.html
標籤：其他
上一篇：四月月賽H題