87. Scramble String
我們可以使用以下算法對字符串 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" // 隨機決定保持兩個子字符串的順序。 算法現在停止，結果字符串是 "rgeat"，即 s2。 由於其中一個可能的場景使得 s1 被混淆為 s2，我們返回 true。
Python
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
memo = {}
def recursiveScramble(s1, s2):
if (s1, s2) in memo:
return memo[(s1, s2)]
if s1 == s2:
memo[(s1, s2)] = True
return True
if sorted(s1) != sorted(s2):
memo[(s1, s2)] = False
return False
n = len(s1)
for i in range(1, n):
# Check if there is a way to split s1 and s2 such that one part is scrambled
if (recursiveScramble(s1[:i], s2[:i]) and recursiveScramble(s1[i:], s2[i:])) or \
(recursiveScramble(s1[:i], s2[-i:]) and recursiveScramble(s1[i:], s2[:-i])):
memo[(s1, s2)] = True
return True
memo[(s1, s2)] = False
return False
return recursiveScramble(s1, s2)
17.35MB,
C++
#include <string>
#include <unordered_map>
class Solution {
public:
bool isScramble(std::string s1, std::string s2) {
std::unordered_map<std::string, bool> memo;
return recursiveScramble(s1, s2, memo);
}
private:
bool recursiveScramble(const std::string& s1, const std::string& s2, std::unordered_map<std::string, bool>& memo) {
std::string key = s1 + " " + s2;
if (memo.find(key) != memo.end()) {
return memo[key];
}
if (s1 == s2) {
memo[key] = true;
return true;
}
if (s1.length() != s2.length() || !areAnagrams(s1, s2)) {
memo[key] = false;
return false;
}
int n = s1.length();
for (int i = 1; i < n; ++i) {
if ((recursiveScramble(s1.substr(0, i), s2.substr(0, i), memo) &&
recursiveScramble(s1.substr(i), s2.substr(i), memo)) ||
(recursiveScramble(s1.substr(0, i), s2.substr(n - i), memo) &&
recursiveScramble(s1.substr(i), s2.substr(0, n - i), memo))) {
memo[key] = true;
return true;
}
}
memo[key] = false;
return false;
}
bool areAnagrams(const std::string& s1, const std::string& s2) {
if (s1.length() != s2.length()) return false;
int count[26] = {0};
for (char c : s1) {
count[c - 'a']++;
}
for (char c : s2) {
if (--count[c - 'a'] < 0) {
return false;
}
}
return true;
}
};
18.99MB, 15ms
Javascript
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var isScramble = function(s1, s2) {
const memo = new Map();
function recursiveScramble(s1, s2) {
const key = s1 + " " + s2;
if (memo.has(key)) {
return memo.get(key);
}
if (s1 === s2) {
memo.set(key, true);
return true;
}
if (!areAnagrams(s1, s2)) {
memo.set(key, false);
return false;
}
const n = s1.length;
for (let i = 1; i < n; i++) {
if (
(recursiveScramble(s1.substring(0, i), s2.substring(0, i)) &&
recursiveScramble(s1.substring(i), s2.substring(i))) ||
(recursiveScramble(s1.substring(0, i), s2.substring(n - i)) &&
recursiveScramble(s1.substring(i), s2.substring(0, n - i)))
) {
memo.set(key, true);
return true;
}
}
memo.set(key, false);
return false;
}
function areAnagrams(s1, s2) {
if (s1.length !== s2.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++) {
count[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
for (let i = 0; i < 26; i++) {
if (count[i] !== 0) {
return false;
}
}
return true;
}
return recursiveScramble(s1, s2);
};
53.26MB, 71ms
