推 Che31128: dp大師 08/25 20:24
推 killheken: 大師 08/25 20:24
推 JerryChungYC: 大師 08/25 20:38
97. Interleaving String
給你三個字串 s1,s2,s3 ，求出是否可以透過交替的插入s1和s2的字元來得到s3。
Example 1:
https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" =
"aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other
string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
思路：
1.選或不選大多都是動態規劃問題，先找幾個簡單的case畫一張表格就可以看出
遞移的方程式了。
2.首先排除明顯不符合的 case，若 s1 和 s2 相加長度不等於 s3 可以直接返回 false。
3.定義dp[i][j] 表示用了 i 個 s1 字元、j 個 s2 的字元組出來的字串是否等於
s3[0,i+j]，要得到當前的 dp[i][j] 只可能有兩種方式組合：
> 用了 i-1 個 s1，j 個 s1 字元，並使用了第 i 個 s1 字元
> 用了 i 個 s1，j -1 個 s2 字元，並使用了第 j 個 s2 字元
如果前一輪組的字串等於 s3 的子字串且當前拿的字串也等於 s3 的下個字串當前就為
true，只要其中一種拿法為真即可（ab 和 ba 不重要）。
4.因為要取前一個所以要初始化第一行和第一列，base case dp[0][0] 為 true，跑完
動態規劃返回 dp[n][m] 即可。
Java Code：
-----------------------------------------
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length();
int m = s2.length();
if (n + m != s3.length()) {
return false;
}
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i <= m; i++) {
dp[0][i] = dp[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char target = s3.charAt(i + j - 1);
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == target) ||
(dp[i][j - 1] && s2.charAt(j - 1) == target);
}
}
return dp[n][m];
}
}
-----------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692966155.A.5D0.html