新博文地址:[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中的匹配是一个道理。
相关推荐
python python_leetcode题解之097_Interleaving_String
c语言基础 c语言_leetcode题解之0097_interleaving_string.zip
js js_leetcode题解之97-interleaving-string.js
在LeetCode平台上,字符串(String)专题是编程爱好者和求职者经常练习的重要部分。这个专题涵盖了字符串处理的各种算法问题,旨在提升编程者对字符串操作的熟练度和理解。在这个压缩包中,"LeetCode-String-master"很...
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 ...
java java_leetcode题解之Magical String.java
python python_leetcode题解之Binary String With Substrings Representing
c语言入门 c语言_leetcode题解perform-string-shifts.c
java java_leetcode题解之Flip String to Monotone Increasing.java
java java_leetcode题解之Construct String from Binary Tree.java
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的函数式的思维逻辑
java java_leetcode题解之Permutation in String.java
java入门 java_leetcode题解之008_String_to_Integer(atoi)
vs code LeetCode 插件
c语言入门 C语言_leetcode题解之08-string-to-integer-atoi.c
《使用leetcode-editor在IDE中进行LeetCode练习的全方位指南》 LeetCode是一个广受欢迎的在线编程练习平台,它提供了一系列的算法题目供程序员们提升技能。对于习惯在集成开发环境(IDE)中工作的开发者来说,将...
《Python版LeetCode题解全集详解》 LeetCode是一个广受欢迎的在线编程挑战平台,致力于帮助程序员提升技能,特别是面试准备。这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的...
"IDEA leetcode-editor插件"就是将这两者结合的工具,允许用户在IDEA中直接进行LeetCode的编程挑战,无需离开开发环境,提高了刷题的便捷性。 该插件的主要功能包括: 1. **离线模式**:在无法访问LeetCode官网的...
js js_leetcode题解之8-string-to-integer-(atoi).js