97. Interleaving String
这是一道极具代表性的字符串动态规划算法题
算法一：暴力递归
public static boolean isInterleave(String s1, String s2, String s3) {return recursive(s1, 0, s2, 0, "", s3);}public static boolean recursive(String s1, int i, String s2, int j, String res, String s3) {if (res.equals(s3) && (i == s1.length()) && (j == s2.length())) {return true;}boolean ans = false;if (i < s1.length())ans |= recursive(s1, i + 1, s2, j, res + s1.charAt(i), s3);if (j < s2.length())ans |= recursive(s1, i, s2, j + 1, res + s2.charAt(j), s3);return ans;}
算法二：记忆化搜索
public static boolean isInterleave1(String s1, String s2, String s3) {int m = s1.length(), n = s2.length();int[][] memo = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++)memo[i][j] = -1;}return recursive1(s1,0,s2,0,s3,0,memo);}public static boolean recursive1(String s1, int i, String s2, int j, String s3, int k, int[][] memo) {if (i == s1.length())return s3.substring(k).equals(s2.substring(j));if (j == s2.length())return s3.substring(k).equals(s1.substring(i));if (memo[i][j] >= 0)return memo[i][j] == 1 ? true : false;boolean ans = false;if ((s1.charAt(i) == s3.charAt(k) && recursive1(s1, i + 1, s2, j, s3, k + 1, memo)) || (s2.charAt(j) == s3.charAt(k) && recursive1(s1, i, s2, j + 1, s3, k+1, memo))) {ans = true;}memo[i][j] = ans ? 1 : 0;return ans;}
算法三：二维DP
public static boolean isInterleave2(String s1, String s2, String s3) {//dp[i][j]int m=s1.length(),n=s2.length();boolean[][] dp=new boolean[m+1][n+1];for(int i=0;i<=m;i++){for(int j=0;j<=n;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(i+j-1);}else if(j==0){dp[i][j]=dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1);}elsedp[i][j]=(dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1)) ||(dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1));}}return dp[m][n];}
算法四：
public class Solution {public boolean isInterleave(String s1, String s2, String s3) {if (s3.length() != s1.length() + s2.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(i + j - 1);} else if (j == 0) {dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 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
static class Coordinate{int x,y;public Coordinate(int x,int y){this.x=x;this.y=y;}}public static boolean isInterleave3(String s1, String s2, String s3){int m=s1.length(),n=s2.length();boolean[][] visited=new boolean[m+1][n+1];Queue<Coordinate> q=new LinkedList<>();q.add(new Coordinate(0,0));while (!q.isEmpty()){Coordinate tmp=q.poll();int x=tmp.x,y=tmp.y;if(x==m && y==n)return true;int down=x+1;if(down<=s1.length() && s1.charAt(down-1)==s3.charAt(down+y-1) && !visited[down][y]){visited[down][y]=true;q.add(new Coordinate(down,y));}int right=y+1;if(right<=s2.length() && s2.charAt(right-1)==s3.charAt(x+right-1) && !visited[x][right]){visited[x][right]=true;q.add(new Coordinate(x,right));}}return false;}