博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 笔记系列 20 Interleaving String [动态规划的抽象]
阅读量:5021 次
发布时间:2019-06-12

本文共 4092 字,大约阅读时间需要 13 分钟。

题目: Given s1s2s3, 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.

这个题目值得记录的原因除了自己的解法没有通过大集合以外,主要还在与对动态规划的理解。在这两个月研究算法的过程中,我发现自己更倾向于直观的理解,而抽象思维上相对较弱。我们以这道题做个例子。

直观上,我看到该题,就会去想,s1取一部分,s2取一部分,然后再s1取一部分,反复知道匹配完成s3,算法去模拟这样的操作。

而当s1和s3匹配了一部分的时候,剩下s1和剩下的s3与s2又是一个子问题。这样很容易写成一个递归,但是需要注意两点:

1. 递归方法中,我们总是拿s1首先去匹配s3,如果不匹配,直接返回false。这样做的原因是保持匹配是“交替”进行的;

2. 当出现既可以匹配s1,又可以匹配s2的时候,一样可以通过递归来解决,看下面的代码。

1 private boolean isInterleaveInternal(String s1, String s2, String s3){ 2         if(s1.equals("")) { 3             return s2.equals("") && s3.equals(""); 4         } 5         if(s1.equals(s3) && s2.endsWith("")) return true; 6         int i1 = 0; 7         int i2 = 0; 8         int i3 = 0; 9         if(s1.charAt(0) != s3.charAt(0)) return false;10         while(i1 < s1.length() && i2 < s2.length() && i3 < s3.length() &&11                 s1.charAt(i1) == s3.charAt(i3)) {12             i1++;13             i3++;14             //如果这里s2也可以匹配s3,那么我们立马递归进行匹配15             if(s2.charAt(i2) == s3.charAt(i3) && isInterleaveInternal(s2.substring(i2), s1.substring(i1), s3.substring(i3)))16                 return true;17         }18         //接下来开始匹配s219         return isInterleaveInternal(s2, s1.substring(i1), s3.substring(i3));20         21     }
View Code

所以在调用这个方法的时候,也比较复杂,需要保证一定是s1首先匹配s3.

1 public boolean isInterleave(String s1, String s2, String s3) { 2         // Start typing your Java solution below 3         // DO NOT write main() function 4         if(s1.length() + s2.length() != s3.length()) return false; 5         if(s1.equals("") || s2.equals("") || s3.equals("")) { 6             if(s3.equals("")) return s1.equals("") && s2.equals(""); 7             else return s1.equals(s3) || s2.equals(s3); 8         } 9         if(s1.charAt(0) == s3.charAt(0)) {10             if(s2.charAt(0) != s3.charAt(0)) {11                 return isInterleaveInternal(s1, s2, s3);12             }else {13                 if(isInterleaveInternal(s1, s2, s3)) return true;14                 else return isInterleaveInternal(s2, s1, s3);15             }16         }else if(s2.charAt(0) == s3.charAt(0)) return isInterleave(s2, s1, s3);17         else return false;18     }
View Code

这个办法看上去蛮直观的,是我马上能想到的,而且也是收到的影响。

但是大集合会超时,而且不好的地方是主函数有挺多的条件判断,显得不够简洁。

于是我们参考了这里的方法。

动态规划矩阵matched[l1][l2]表示s1取l1长度(最后一个字母的pos是l1-1),s2取l2长度(最后一个字母的pos是l2-1),是否能匹配s3的l1+12长度。

那么,我们有

matched[l1][l2] = s1[l1-1] == s3[l1+l2-1] && matched[l1-1][l2] || s2[l2 - 1] == s3[l1+l2-1] && matched[l1][l2-1]

边界条件是,其中一个长度为0,另一个去匹配s3.

这里s1和s2交替出现的规律并不明显,所以没有直观地想到。

代码如下:

1 public boolean isInterleave2(String s1, String s2, String s3){ 2         if(s1.length() + s2.length() != s3.length()) return false; 3         boolean[][] matched = new boolean[s1.length() + 1][s2.length() + 1]; 4         matched[0][0] = true; 5         for(int i1 = 1; i1 <= s1.length(); i1++){ 6             if(s3.charAt(i1-1) == s1.charAt(i1-1)) { 7                 matched[i1][0] = true; 8             }else break; 9         }10         for(int i2 = 1; i2 <= s2.length(); i2++){11             if(s3.charAt(i2 - 1) == s2.charAt(i2 - 1)) {12                 matched[0][i2] = true;13             }else break;14         }15         16         for(int i1 = 1; i1 <= s1.length(); i1++){17             char c1 = s1.charAt(i1 - 1);18             for(int i2 = 1; i2 <= s2.length(); i2++){19                 int i3 = i1 + i2;20                 char c2 = s2.charAt(i2 - 1);21                 char c3 = s3.charAt(i3 - 1);22                 if(c1 == c3){23                     matched[i1][i2] |= matched[i1 - 1][i2];24                 }25                 if(c2 == c3){26                     matched[i1][i2] |= matched[i1][i2 - 1];27                 }28             }29         }30         return matched[s1.length()][s2.length()];31     }
View Code

总结下:

1)递归能写出比较清晰简单的代码,但是有比较高的时间复杂度;

2)在递归不满足条件的情况下,动态规划是个比较好的选择;

3)一般来说,独立变量的个数决定动态规划的维度,例如l1和l2独立变化,所以用了二维动态规划。

 

转载于:https://www.cnblogs.com/lichen782/p/leetcode_interleaving_string.html

你可能感兴趣的文章
T-SQL查询进阶--深入浅出视图
查看>>
MapKeyboard 键盘按键映射 机械革命S1 Pro-02
查看>>
Android读取url图片保存及文件读取
查看>>
完整ASP.Net Excel导入
查看>>
判断CPU大小端示例代码
查看>>
ARTS打卡第13周
查看>>
循环队列的运用---求K阶斐波那契序列
查看>>
pta 编程题14 Huffman Codes
查看>>
初始化bootstrap treeview树节点
查看>>
python selenium向<sapn>标签中写入内容
查看>>
JS常用坐标
查看>>
使用”结构化的思考方式“来编码和使用”流程化的思考方式“来编码,孰优孰劣?...
查看>>
C#调用斑马打印机打印条码标签(支持COM、LPT、USB、TCP连接方式和ZPL、EPL、CPCL指令)【转】...
查看>>
关于git的认证方式
查看>>
字符串按照字典序排列
查看>>
IOS 开发调用打电话,发短信
查看>>
CI 框架中的日志处理 以及 404异常处理
查看>>
keepalived介绍
查看>>
css3 标签 background-size
查看>>
python itertools
查看>>