`
huntfor
  • 浏览: 201068 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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中的匹配是一个道理。

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics