版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434856
之前有一篇博文专门讲了什么是动态规划,但发现哪怕是理解了什么是动态规划,在实际刷题时也遇到了很多麻烦。究其原因,对动规的理解还不够透彻,其次对状态的递归和迭代的转化不够熟练,所以遇到一个问题时,无法立刻写出递推式。本篇重在讨论如何利用递归技术实现记忆化搜索,在此基础上呈现问题从递归到迭代的转换,即动态规划。
以下题目摘自leetcode的Word Break系列,简单来说,就是让字典里的单词组成一个字符串,或者说检查字符串是否划分成字典里的多个单词,来看道题。
Problem:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s = “leetcode”, dict = “leet”, “code”. Return true because “leetcode” can be segmented as “leet code”.
最navie的想法,就是让dict
中的单词去匹配字符串,所以我们可以很容易想到一种递归,如找到leet
,那么再拿剩下的code
去dict
中找,如果找到就返回true
。
所以一种简单的递归结构是:
1. 从字符串s中找出一个dict,如果dict在中间,则划分成左半部分和右半部分。
2. 分别对左半部分和右半部分做相同的递归操作。
3. 直到字符串为空,则返回true
这是我的思路,但里面存在很多问题,如为什么找出的dict会在s
的中间,能否规避这种情况?其次,这种解法本身符合所有测试用例么?
我们看一个测试用例:
s="abcdeefg" dict=["ab","cde","ee","cd","fg"]
加入我们选取了字典中的cde
,那么所导致的分割为ab
和efg
,而在这种情况下,子问题将返回false,所以上述思路是明显不能适应所有情况。
我们最初的想法是从字典中找寻单词去匹配字符串,但其实我们可以反过来思考,假设待匹配的字符串能由字典组成了,那么我们就可以从字符串头开始寻找对应的单词。如s = "abcdeefg"
,遍历字典,总能找到ab
,这样我们可以把字符串划分为子字符串cdeefg
进行递归查找。
这种方法就能很好的支持字符串中出现多个字典匹配的情况,如处理cdeefg
的匹配问题时,我们实际可以找到cd
和cde
两种模式,而对应的子子问题分别是eefg
和efg
,这种方案就能遍历字典集,而不会出现漏检的情况。所以像这样的问题,递归中一定含有多个子递归。代码如下:
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s, wordDict);
}
private boolean wordBreak(String s, List<String> wordDict) {
if (s.length() == 0) return true;
//针对每一种可能的划分情况
for (int i = 1; i <= s.length(); i++){
String ss = s.substring(0, i);
if (wordDict.contains(ss) && wordBreak(s.substring(i,s.length()),wordDict,mem)){
return true;
}
}
return false;
}
这是一种解决方案,遍历对象为我们的字符串。当然,我们也可以以字典为遍历对象,从字典中找寻符合的字符串进行划分,可以写成如下:
for (String ss : wordDict){
if (s.startsWith(ss) && wordBreak(s.substring(ss.length()), wordDict, mem)) return true;
}
但不管是哪种方案,你会发现在递归中出现了多个子问题,遇到多个子问题,咱们就可以考虑是否能用记忆化手段解决。原因很简单,多个子问题中,在递归时有可能会出现重复子问题。所以上述代码会TLE!
记忆方法代码如下:
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> mem = new HashSet<>();
return wordBreak(s, wordDict,mem);
}
private boolean wordBreak(String s, List<String> wordDict, Set<String> mem) {
if (s.length() == 0) return true;
if (mem.contains(s)) return false;
mem.add(s);
//针对每一种可能的划分情况
for (int i = 1; i <= s.length(); i++){
String ss = s.substring(0, i);
if (wordDict.contains(ss) && wordBreak(s.substring(i,s.length()),wordDict,mem)){
return true;
}
}
return false;
}
它的记忆化非常巧妙,观察代码你会发现,主要是为了规避相同的子问题求解,减少递归,而在if
语句中,我们的第一守卫是wordDict.contains(ss)
,他负责把不需要的情况排除,但是它没有做到一点,如:
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
dict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa"]
不管该答案最后能不能被划分,刚进入递归,符合第一守卫的条件为:
1. a
2. aa
3. aaa
4. aaaa
5. aaaaa
6. aaaaaa
这六种情况,都会形成六个子问题继续递归,就拿第一种情况来说,它下一子问题的递归数量还是6种情况,因为守卫条件单纯的只是拿字典中的单词匹配,所以它的最坏情况就是O(6n)O(6^n),n是字符串s
的长度。那么一个简单的想法就是记录所有匹配成功的情况,让这些成功匹配的字符串“加入”字典中,但发现它实际很难操作,因为它是自顶向下去搜索答案的,在搜索的过程中,我们并不知道哪条路径上的字符串是匹配成功的,直到遍历结束返回时我们才能拿到匹配成功的字符串。
所以本题的记忆化很奇特,返回的是false
,我刚开始一直不明白咋记录了错误的结果!其实它所记录的都是还未匹配的字符串。如初始条件,记录的就是最原始的字符串,它还未匹配。简单说说它为什么能work,再举个简单点的例子:(后来发现,它还是最单纯的记忆手段,记录状态和函数返回值)
s = "aaaaa"
dict = ["a","aa","aaa"]
第一次递归,会出现三种可能的子问题,未匹配字符串为
递归层数 1 递归层数 2
匹配 未匹配 匹配 未匹配
a aaaa a aaa
aa aaa ... ...
aaa aa ... ...
你要一一举出的话,在递归层数2中有9种情况,我们可以看看递归层数1中和递归层数2中,在未匹配字符串上出现了子问题,所以早在不断遍历a
的过程当中,就记录了一次aaa
未匹配的值,而当从aa
发展子问题时,就可以直接返回false
,因为我们在a
的递归问题中做过该问题了,如果a
中有路径发展成true,那么自然不会遗留给aa
去做,所以aa
关于未匹配的aaa
没必要去搜索了。
说了那么多,总结一下,该问题可以用递归+记忆化的手段去做,但做递归时,我们可以利用路径搜索的有序性,把每层的【未匹配字符串】记录下来,所利用的依据就是说,【同样的字典集】,某个递归发展的子问题你解决不了,那么以其他递归发展下来的相同子问题,你也解决不了。
有了递归记忆搜索的解决方案,我们再来看看动规是如何解决该问题的,很有趣,它们互为逆向过程,刚才递归的尴尬在于无法在搜索路径上确定哪些答案是正确的,这难道是动规引出的后效性原理?哈哈,还不理解。现在做到的递归多数是不到最后一刻不知道结果的尴尬情景,那么动规能解决什么问题?
新的认识:自底向上的构建结果,在构建过程中,有能力把中间状态记录下来,而自底是关键,你也能从代码上看出很大的区别,递归方案的循环较少,而动规的循环却如此吓人,因为动规从底构建解啊,它并不知道到底那个方案是正确的,所以刚开始一定得把每种状态考虑进去。此时,我们再来看看动规的解决方案,就有了一种新的认识,千万别拿代码去验证答案,对解决问题绝对无用!
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] f = new boolean[s.length()+1];
f[0] = true;
for (int i = 1; i <= s.length(); i++){
for (int j = 0; j < i; j++){
if(f[j] && wordDict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[s.length()];
}
好了,现在我们从动规的结构去认识该问题,动规需要明确三点:
就从递归的解决方案来看,它的状态就是待匹配的字符串true or false
,所以可行的方案就是map.put(s,canForm ? true: false)
,但需要使用map么?字符串匹配的状态可以由当前字符串的长度唯一记录。这种信息的约简很神奇,有悖于人类思维。比如说:s= "leetcode","leecode"
,我们给了dict = {"leet","code"}
,很明显leetcode
能够成功匹配,而我们做匹配时,始终把leet放在了眼里,但一旦匹配成功,我们需要l,e,e,t
的信息么?关键问题就在于某个问题一旦被你解决,它的冗余信息就可以被去除,这是动规难以理解的原因之一,状态的值很容易求解,但如果确保状态和值之间是唯一对应就成了难点。上述问题,我们可以用位置去代表状态和值之间的关系,所以有了连续字符串长度来代表状态值。
boolean[] f = new boolean[s.length()+1]
注意它的连续性,它深刻的决定了遍历的顺序。好了,状态明确了,现在再来看看代码,似乎就能理解它的深刻含义了,首先循环结构:
for (int i = 1; i <= s.length(); i++){
for (int j = 0; j < i; j++){
// ......
}
}
因为我们不知道到底哪种prefix
最终形成解,所以得把所有情况给遍历一次,也就有了两层循环的结构。
遍历顺序一定是prefix
遍历(假设待匹配字符串是正确的搜索方案),状态如何改变呢?subString(j,i)
也很有特点,除了遍历所有可能的prefix
以外,还需要遍历postfix
,为的就是在最底层把所有情况都考虑进来,乍一看该循环特别吓人,但别忘了守卫条件,首先不管是前缀后缀,都必须出现在字典集中,其次哪怕后缀匹配成功,也得保证后缀的前缀必须已经匹配成功,否则不去更新!所以可以想象,这种暴力的做法虽然看着非常吓人,但一大部分遍历是被屏蔽的。
总结:
Problem:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s = “catsanddog”, dict = “cat”, “cats”, “and”, “sand”, “dog”. A solution is “cats and dog”, “cat sand dog”.
吼吼,这道题是状态记录的升级版,现在要求把所有可能的路径给求出来。
public List<String> wordBreak(String s, List<String> wordDict) {
return canForm(s, wordDict, new HashMap<>());
}
private List<String> canForm(String s, List<String> wordDict, Map<String, List<String>> map){
if (map.containsKey(s)) return map.get(s);
List<String> ans = new ArrayList<>();
if (s.length() == 0){
ans.add("");
return ans;
}
for (String word : wordDict){
if (s.startsWith(word)){
List<String> subList = canForm(s.substring(word.length()), wordDict, map);
for (String sub : subList){
ans.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
}
map.put(s, ans);
return ans;
}
理解了word break ,这道题也就不难理解,原先我们递归结束时,返回true,并且让true一层层向上传递。而此时,递归能结束(说明匹配一定成功),那么递归返回时,把所有结果记录在list中即可。此时,返回的结果不是单纯的true or false
,所以用map来存放键值对。
Problem:
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Input: “cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat” Output: “catsdogcats”,”dogcatsdog”,”ratcatdogcat” Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;undefined “dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;undefined “ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.
Note:
一个道理,输入中混杂了字典和匹配单词,所以直接从输入中筛选即可,筛选规则就是word break中的方法,如果能够匹配,就加入到list中。
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ans = new ArrayList<>();
Set<String> set = new HashSet<>();
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
for (int i = 0; i < words.length;i++){
if(wordBreak(words[i],set)){
ans.add(words[i]);
}
set.add(words[i]);
}
return ans;
}
//139. Word Break
private boolean wordBreak(String s, Set<String> wordDict){
if(wordDict.isEmpty()) return false;
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for (int i = 1; i <= s.length(); i++){
for (int j = 0; j < i; j++){
if (f[j] && wordDict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[s.length()];
}
筛选过程中,做了些许优化,很容易理解。单词按长度排序,长度小的一定不能由长度大的单词组成,自己不能组成自己。所以,我们才可以用一个单循环完成这些判别操作。