首页 > 代码库 > Interleaving String

Interleaving String

Given s1, s2, s3, find whethers3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

最简单思路就是递归去做,但是这样需要递归最多s3长度的层次,消耗比较大,很容易出现超时错误,进行递归尝试果然出现超时错误,但是递归是解决这个问题最直观的方法。

递归方法不行考虑DP,我们用path[i][j] 记录s1到i 和s2到j 和s3[i+j-1]是否满足要求,这个过程就是填一张二维数组表的过程,先初始化第一行和第一列,然后填表计算出所有,返回path[s1.length][s2.length]的值。

已经AC的代码:

public class Solution {    	public boolean isInterleave(String s1, String s2, String s3) {		if(s1.length()+s2.length()!=s3.length()){			return false;		}		int row = s1.length();		int col = s2.length();		boolean [][]path = new boolean[row+1][col+1];		path[0][0] = true;		for(int i=1;i<=row;i++){			path[i][0] = path[i-1][0] && (s1.charAt(i-1)==s3.charAt(i-1));		}		for(int i=1;i<=col;i++){			path[0][i] = path[0][i-1] && (s2.charAt(i-1) == s3.charAt(i-1));		}		for(int i=1;i<=row;i++){			for(int j=1;j<=col;j++){				path[i][j] = (path[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) ||						(path[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));			}		}		return path[row][col];	}}


 

Interleaving String