87. Scramble String
C# 解法
照合済み/オリジナルpublic class Solution {
public bool IsScramble(string s1, string s2) {
int n = s1.Length;
bool[][][] dp = new bool[n + 1][][];
for (int i = 0; i < dp.Length; i++) {
dp[i] = new bool[n][];
for (int j = 0; j < dp[i].Length; j++) {
dp[i][j] = new bool[n];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[1][i][j] = s1[i] == s2[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++) {
bool[] dp1 = dp[newLength][i];
bool[] 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];
}
}C++ 解法
自動ドラフト、提出前に確認#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool IsScramble(string s1, string s2) {
int n = s1.size();
bool[][][] dp = new bool[n + 1][][];
for (int i = 0; i < dp.size(); i++) {
dp[i] = new bool[n][];
for (int j = 0; j < dp[i].size(); j++) {
dp[i][j] = new bool[n];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[1][i][j] = s1[i] == s2[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++) {
bool[] dp1 = dp[newLength][i];
bool[] 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];
}
}Java 解法
照合済み/オリジナル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];
}
}JavaScript 解法
照合済み/オリジナルvar isScramble = function (s1, s2) {
const n = s1.length;
let dp = new Array(n + 1)
.fill(0)
.map(() => new Array(n).fill(0).map(() => new Array(n).fill(false)));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
}
}
for (let length = 2; length <= n; length++) {
for (let i = 0; i < n + 1 - length; i++) {
for (let j = 0; j < n + 1 - length; j++) {
for (let newLength = 1; newLength < length; newLength++) {
const dp1 = dp[newLength][i];
const 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];
};Python 解法
照合済み/オリジナルclass Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
dp = [
[[False for j in range(n)] for i in range(n)] for l in range(n + 1)
]
for i in range(n):
for j in range(n):
dp[1][i][j] = s1[i] == s2[j]
for length in range(2, n + 1):
for i in range(n + 1 - length):
for j in range(n + 1 - length):
for new_length in range(1, length):
dp1 = dp[new_length][i]
dp2 = dp[length - new_length][i + new_length]
dp[length][i][j] |= dp1[j] and dp2[j + new_length]
dp[length][i][j] |= (
dp1[j + length - new_length] and dp2[j]
)
return dp[n][0][0]Go 解法
照合済み/オリジナルfunc isScramble(s1 string, s2 string) bool {
n := len(s1)
dp := make([][][]bool, n+1)
for i := range dp {
dp[i] = make([][]bool, n)
for j := range dp[i] {
dp[i][j] = make([]bool, n)
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
dp[1][i][j] = s1[i] == s2[j]
}
}
for length := 2; length <= n; length++ {
for i := 0; i < n+1-length; i++ {
for j := 0; j < n+1-length; j++ {
for newLength := 1; newLength < length; newLength++ {
dp1 := dp[newLength][i]
dp2 := dp[length-newLength][i+newLength]
dp[length][i][j] = dp[length][i][j] ||
(dp1[j] && dp2[j+newLength])
dp[length][i][j] = dp[length][i][j] ||
(dp1[j+length-newLength] && dp2[j])
}
}
}
}
return dp[n][0][0]
}Algorithm
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.
- return dp[n][0][0].
😎
Vacancies for this task
有効な求人 with overlapping task tags are 表示.