本文已参加「新人创造礼」活动,一同敞开创造之路。
leetcode第97题
题目描绘(中等难度)
在两个字符串 s1 和 s2 中依次取字母,问是否能够组成 S3。什么意思呢?比方 s1 = abc , s2 = de,s3 = abdce。
s1 取 1 个 字母得到 a,s1 再取个字母得到 ab,s2 取个字母得到 abd, s1 取 1 个 字母得到 abdc, s2 取 1 个 字母得到 abdce,然后就得到了 s3,所以回来 true。
解法一 回溯法
假如咱们简化下问题,假如 s1 和 s2 中不含有重复的字母,比方 s1 = abc,s2 = de,s3 = abdce。
i 和 k 的指的字母持平,所以 i 后移,k 后移
a b c
^
i
d e
^
j
a b d c e
^
k
i 和 k 的指的字母持平,所以 i 后移,k 后移
a b c
^
i
d e
^
j
a b d c e
^
k
j 和 k 的指的字母持平,所以 j 后移,k 后移
a b c
^
i
d e
^
j
a b d c e
^
k
就这样比较下去,假如 i,j,k 都成功移动到了结尾即成功。
但是这道题 s1 和 s2 中会有重复的字符出现,比方下边的状况
a d c
^
i
d e
^
j
a d c e
^
k
此刻 i 和 j 指向的字母都和 k 持平,此刻该怎么办呢?
回溯法!是的,咱们先测验 i 和 k 后移,然后看能不能成功。不行的话咱们再回溯回来,把 j 和 k 后移。
public boolean isInterleave(String s1, String s2, String s3) {
return getAns(s1, 0, s2, 0, s3, 0);
}
private boolean getAns(String s1, int i, String s2, int j, String s3, int k) {
//长度不匹配直接回来 false
if (s1.length() + s2.length() != s3.length()) {
return false;
}
// i、j、k 悉数达到了结尾就回来 true
if (i == s1.length() && j == s2.length() && k == s3.length()) {
return true;
}
// i 抵达了结尾,直接移动 j 和 k 不断比较
if (i == s1.length()) {
while (j < s2.length()) {
if (s2.charAt(j) != s3.charAt(k)) {
return false;
}
j++;
k++;
}
return true;
}
// j 抵达了结尾,直接移动 i 和 k 不断比较
if (j == s2.length()) {
while (i < s1.length()) {
if (s1.charAt(i) != s3.charAt(k)) {
return false;
}
i++;
k++;
}
return true;
}
//判别 i 和 k 指向的字符是否持平
if (s1.charAt(i) == s3.charAt(k)) {
//后移 i 和 k 继续判别,假如成功了直接回来 true
if (getAns(s1, i + 1, s2, j, s3, k + 1)) {
return true;
}
}
//移动 i 和 k 失利,测验移动 j 和 k
if (s2.charAt(j) == s3.charAt(k)) {
if (getAns(s1, i, s2, j + 1, s3, k + 1)) {
return true;
}
}
//移动 i 和 j 都失利,回来 false
return false;
}
让咱们优化一下,由于递归的分支,所以会造成很多重复状况的判别,所以咱们用 memoization 技术,把求出的成果用 hashmap 保存起来,第2次过来的时分直接回来成果以免再次进入递归。
用 1 表明 true,0 表明 false,-1 代表还未赋值。
hashmap key 的话用字符串 i + “@” + j ,之所以中间加 “@”,是为了避免 i = 1 和 j = 22。以及 i = 12,j = 2。这样的两种状况发生的就都是 122。加上 “@” 能够区分开来。
public boolean isInterleave(String s1, String s2, String s3) {
HashMap<String, Integer> memoization = new HashMap<>();
return getAns(s1, 0, s2, 0, s3, 0, memoization);
}
private boolean getAns(String s1, int i, String s2, int j, String s3, int k, HashMap<String, Integer> memoization) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
String key = i + "@" + j;
if (memoization.containsKey(key)) {
return memoization.getOrDefault(key, -1) == 1;
}
if (i == s1.length() && j == s2.length() && k == s3.length()) {
memoization.put(key, 1);
return true;
}
if (i == s1.length()) {
while (j < s2.length()) {
if (s2.charAt(j) != s3.charAt(k)) {
memoization.put(key, 0);
return false;
}
j++;
k++;
}
memoization.put(key, 1);
return true;
}
if (j == s2.length()) {
while (i < s1.length()) {
if (s1.charAt(i) != s3.charAt(k)) {
memoization.put(key, 0);
return false;
}
i++;
k++;
}
memoization.put(key, 1);
return true;
}
if (s1.charAt(i) == s3.charAt(k)) {
if (getAns(s1, i + 1, s2, j, s3, k + 1, memoization)) {
memoization.put(key, 1);
return true;
}
}
if (s2.charAt(j) == s3.charAt(k)) {
if (getAns(s1, i, s2, j + 1, s3, k + 1, memoization)) {
memoization.put(key, 1);
return true;
}
}
memoization.put(key, 0);
return false;
}
解法二 动态规划
参考这儿。
其实和递归本质上是相同的,解法一中压栈到结尾最终一个字符的时分,再次压栈,就会进入 if (i == s1.length() && j == s2.length() && k == s3.length()) 这儿,然后就开端一系列的出栈进程。
而动态规划就是利用一个 dp 数组去省去压栈,所谓空间换时刻。这儿的话,咱们也不模仿递归从尾部开端了,咱们直接从开头开端,思维是相同的。
咱们定义一个 boolean 二维数组 dp [ i ] [ j ] 来表明 s1[ 0, i ) 和 s2 [ 0, j ) 组合后能否构成 s3 [ 0, i + j ),留意不包括右鸿沟,主要是为了考虑开端的时分假如只取 s1,那么 s2 就是空串,这样的话 dp [ i ] [ 0 ] 就能表明 s2 取空串。
状况转化方程也很好写了,假如要求 dp [ i ] [ j ] 。
假如 dp [ i – 1 ] [ j ] == true,而且 s1 [ i – 1 ] == s3 [ i + j – 1], dp [ i ] [ j ] = true 。
假如 dp [ i ] [ j – 1 ] == true,而且 s2 [ j – 1 ] == s3 [ i + j – 1], dp [ i ] [ j ] = true 。
不然的话,就更新为 dp [ i ] [ j ] = false。
假如 i 为 0,或许 j 为 0,那直接判别 s2 和 s3 对应的字母或许 s1 和 s3 对应的字母即可。
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
} else {
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
|| dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
}
}
}
return dp[s1.length()][s2.length()];
}
然后就是老规矩了,空间复杂度的优化,例如5题,10题,53题,72题等等都是相同的思路。都是留意到一个特色,当更新到 dp [ i ] [ j ] 的时分,咱们只用到 dp [ i – 1 ] [ j ] ,即上一层的数据,再之前的数据就没有用了。所以咱们不需要二维数组,只需要一个一维数组就够了。
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[] dp = new boolean[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
dp[j] = true;
} else if (i == 0) {
dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
} else if (j == 0) {
dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i - 1);
} else {
dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
|| dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
}
}
}
return dp[s2.length()];
}
解法三 广度优先遍历 BFS
参考这儿。咱们把问题笼统一下。
从左上角抵达右下角,遍历进程加上边对应的字符,最终就能够发生 S3 了。回想一下,解法一递归的遍历进程,其实就是图的深度遍历,从 0 位置动身,共同测验向右,不行的话就回溯,再测验向下,然后再开端测验向右,直到右下角。像一只贪婪的蛇,认准方针直奔而去。
而解法一开端没有优化前讲到说会有很多重复的解,结合上边的图也刚好理解了。由于开端测验了条路后,回退回退回退,然后再向前的时分就可能回到原来的路上了。
这儿的话,已然都现已笼统出一个图了,所以除了 DFS,当然还有 BFS。测验遍历整个图,假如抵达了右下角就回来 true。
当然恣意两个节点并不是都能够抵达的,只有当前要遍历的 S1 或许 S2 对应的字母和 S3 相应的字母持平咱们才能够遍历。
用一个行列保存能够遍历的节点,然后不断的从行列里取元素,然后把能够抵达的新的节点加到行列中。
class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(0, 0));
//判别是否现已遍历过
boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1];
while (!queue.isEmpty()) {
Point cur = queue.poll();
//抵达右下角就回来 true
if (cur.x == s1.length() && cur.y == s2.length()) {
return true;
}
// 测验是否能向右走
int right = cur.x + 1;
if (right <= s1.length() && s1.charAt(right - 1) == s3.charAt(right + cur.y - 1)) {
if (!visited[right][cur.y]) {
visited[right][cur.y] = true;
queue.offer(new Point(right, cur.y));
}
}
// 测验是否能向下走
int down = cur.y + 1;
if (down <= s2.length() && s2.charAt(down - 1) == s3.charAt(down + cur.x - 1)) {
if (!visited[cur.x][down]) {
visited[cur.x][down] = true;
queue.offer(new Point(cur.x, down));
}
}
}
return false;
}
总结
很经典的一道题了,第一次用到了 BFS,之前都是 DFS。最终的图,其实把所有的解法的本质都揭露了出来。