Сложность: hard
Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
1. Если длина строки равна 1, остановиться.
2. Если длина строки больше 1, выполнить следующее:
- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.
- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.
- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.
Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.
Пример:
Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
👨💻 Алгоритм:
1⃣Итерируйте i от 0 до n-1.
- Итерируйте j от 0 до n-1.
- Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования).
2⃣Итерируйте length от 2 до n.
- Итерируйте i от 0 до n + 1 - length.
- Итерируйте j от 0 до n + 1 - length.
3⃣Итерируйте newLength от 1 до length - 1.
- Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true.
- Верните dp[n][0][0].
😎 Решение:
class Solution {
public boolean isScramble(String s1, String s2) {
int n = s1.length();
boolean dp[][][] = new boolean[n + 1][n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
}
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i < n + 1 - length; i++) {
for (int j = 0; j < n + 1 - length; j++) {
for (int newLength = 1; newLength < length; newLength++) {
boolean dp1[] = dp[newLength][i];
boolean dp2[] = dp[length - newLength][i + newLength];
dp[length][i][j] |= dp1[j] && dp2[j + newLength];
dp[length][i][j] |=
dp1[j + length - newLength] && dp2[j];
}
}
}
}
return dp[n][0][0];
}
}Ставь 👍 и забирай 📚 Базу знаний