[leetcode]Interleaving String

新博文地址：[leetcode]Interleaving String

建议大家看新博文，自己想的算法比本博文借鉴的算法要更容易理解。

Interleaving String

Given s1, s2, s3, find whether s3 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.

题目大意： 两个字符串能否交织生成第三个串

本来这道题用递归，貌似很容易实现，但是大数据超时了，后来翻了一下本题难度系数5，实在是扮猪吃虎啊。好吧，剩下的这几道题我都不会，都需要看别人的思路。这道题有位FB大神，用了十几行代码就搞定了，下面就他的算法简单分析一下：

先贴出自己最初的代码做一个引子：

 

  public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() == 0){
        	if( s2.equals(s3))return true;
        	else return false;
        }else if(s2.length() == 0){
        	if(s1.equals(s3)) return true;
        	else return false;
        }
        if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0) != s2.charAt(0)){
        	return isInterleave(s1.substring(1), s2, s3.substring(1));
        }else if(s3.charAt(0) == s2.charAt(0) && s3.charAt(0) != s1.charAt(0)){
        	return isInterleave(s1, s2.substring(1), s3.substring(1));
        }else if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)){
        	return isInterleave(s1.substring(1), s2, s3.substring(1)) || isInterleave(s1, s2.substring(1), s3.substring(1));
        }else{
        	return false;
        }
    }

 想法很单纯，相同的字符就delete比余下子串，如果两个都相同，分别delete，求或。但是对于大数据超时了。因此需要记录delete的中间状态省的做多余操作。DP。看到有位大神用了剪枝策略，递归搞定，感兴趣的可以戳这里（下面有人评论中提出了剪枝策略）。言归正传，本题借用了FB大神用了DP算法，原博文戳这里。

 

代码如下：

 

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

 据我的理解，hash记录的是s1,s2到s3的可达性，这里采用了贪心的策略，尽量往后与s3匹配的。

 

因此有了这个：

for(int i = 1; i <= s1.length(); i++)
	hash[0][i] = hash[0][i - 1] && (s1.charAt(i - 1) == s3.charAt(i - 1));

还有这个

for(int i = 1; i <= s2.length(); i++)
	hash[i][0] = hash[i - 1][0] && (s2.charAt(i - 1) == s3.charAt(i - 1))

 该初始化表示，单个字符串可以匹配的长度。

下面开始对两个字符串进行交织匹配：

for(int i = 1; i <= s2.length(); i++){
			for(int j = 1; j <= s1.length(); j++){
				hash[i][j] = (hash[i - 1][j] && (s2.charAt(i - 1) == s3.charAt(i + j - 1)) )|| (hash[i][j - 1] && (s1.charAt(j - 1) == s3.charAt(i + j -1)));
			}
		}

大家来看这个例子：其中s1 = aca，s2 = aab, s3 = aacaba

s2↓           s1→	0	a	c	a
0		1	1	1
a	1	1
a	1
b	0

经过初始化之后，矩阵如图所示，其中可以将1看做是一条路径，表示这条路径都是可匹配的。

hash[i - 1][j]，hash[i][j - 1]表示s3中前i + j - 1已经匹配成功，其中hash[i][j - 1]表示往右匹配，例如图中红色的1，表示左边的1是匹配的，即上一步s2的a被delete了，同理hash[i - 1][j]表示上一步s1中的a被delete了。s2.charAt(i - 1) == s3.charAt(i + j - 1) 和s1.charAt(j - 1) == s3.charAt(i + j -1)不用过多解释，去寻找可以匹配s3开头的字符，如果a中的第i个字符与之匹配，则检查a的第i-1个字符是否是可达的。同理b中的匹配是一个道理。