文章目录
思考自顶向下解决问题的模式95. Unique Binary Search Trees题目链接题意思路
140. Word Break II题目链接题意思路
思考自顶向下解决问题的模式
95. Unique Binary Search Trees
题目链接
leetcode 95. Unique Binary Search Trees
题意
给定一个整数n，输出把1到n所有值作为树结点的所有可能的二叉搜索树的组合。
思路
二叉搜索树的定义：左边结点的值 < 根节点的值 < 右边结点的值。那么根据根节点的不同，1到n的所有值尽可能作为根节点。这里我们不妨假设k(1<=k<=n)为某一颗二叉搜索树的根节点。那么左子树的根节点的可能值为[1,k-1]，右子树的根节点的所有可能值为[k+1,n]。
难点在于怎么在[1,k-1]，[k+1,n]继续遍历子树的所有左右子树，直接列举所有情况显然是不现实的，这时候我们采用自顶向下的思想，将[1,k-1]，[k+1,n]的所有情况放在栈（存储子问题用到的临时变量）中，最后逐步合并所有可能的情况即可。
class Solution {
public:
vector
<TreeNode
*> generateTrees(int n
){
vector
<TreeNode
*> ans
;
if(n
==0) return ans
;
return solve(1,n
);
}
vector
<TreeNode
*> solve(int l
,int r
){
vector
<TreeNode
*> ans
;
if(l
>r
){
ans
.push_back(NULL);
return ans
;
}
for(int i
=l
;i
<=r
;i
++){
vector
<TreeNode
*> left
=solve(l
,i
-1);
vector
<TreeNode
*> right
=solve(i
+1,r
);
for(TreeNode
* le
: left
){
for(TreeNode
*ri
:right
){
TreeNode
* root
=new TreeNode(i
);
root
->left
=le
;
root
->right
=ri
;
ans
.push_back(root
);
}
}
}
return ans
;
}
140. Word Break II
题目链接
leetcode 140. Word Break II
题意
给定一个字典，判断一个字符串能被断句成多少种可能的情况
思路
首先利用一个set保存词典里面所有出现的词，这样在后续断句的时候能以O(1)的复杂度判断单词是否在词典中然后就是断句，给定一个字符串s = “catsanddog”，给定词典 wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]，如何寻求所有可能的断句方式？我们可以采用类似上面一题的思想，将这个单词先分成左右两部分，比如将s分成"cat"和"sanddog"，那么原问题就变成判断"cat"是否在词典wordDict中，以及"sanddog"的子字符串是否在词典中，这样依次类推下去。对于本题还要采用记忆化搜索剪枝（用一个map存储一下已经遍历字符串的结果），避免右边部分字符串的子问题反复判断是否在词典中
class Solution {
public:
unordered_map
<string
,vector
<string
>> ump
;
vector
<string
> wordBreak(string s
, vector
<string
>& wordDict
) {
vector
<string
> ans
;
if(!s
.size() || !wordDict
.size()) return ans
;
set
<string
> S
;
for(string str
:wordDict
){
if(!S
.count(str
)){
S
.insert(str
);
}
}
return solve(s
,S
);
}
bool Containr(set
<string
> S
,string str
){
for(int i
=1;i
<=str
.size();i
++){
string tmp
=str
.substr(0,i
);
if(S
.count(tmp
)) return true;
}
return false;
}
vector
<string
> solve(string s
, set
<string
> S
){
if(ump
.count(s
)) return ump
[s
];
vector
<string
> ans
;
if(S
.count(s
)) ans
.push_back(s
);
for(int i
=1;i
<s
.size();i
++){
string left
=s
.substr(0,i
);
string right
=s
.substr(i
);
if(S
.count(left
) && Containr(S
,right
) ){
for(string r
: solve(right
,S
)){
ans
.push_back(left
+" "+r
);
}
}
}
ump
[s
]=ans
;
return ans
;
}
};
本题思路参考：https://leetcode.com/problems/word-break-ii/discuss/44179/Slightly-modified-DP-Java-solution
