新博文地址:[leetcode]Interleaving String
建议大家看新博文,自己想的算法比本博文借鉴的算法要更容易理解。
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中的匹配是一个道理。
相关推荐
leetcode 答案 LeetCode-String #这是LeetCode里面String专题中的python版答案
Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input ...
leetcode字符串转换为整数
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Reverse words in a string-leetcode
"interleaving_string.erl","search_insert_position.erl", "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
100个leetCode详细解答
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 双指针 编号 题目 LeetCode 11 Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 ...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。