这道题,我们需要先通过把单词录入哈希表。然后构造一个可达性DP,dp[i] 代表了 s[0..i] 是否能拆分成 wordsDict 中的单词,再通过可达性 DP 构造一个 prevs 数组记录从某个位置 j 能够构造出的多个单词起点 i 的关系图。最后通过回溯 DFS,从尾部开始向前搜索 prevs 数组,一直遍历到头,得到的 path 一定是一个涵盖 wordsDict 单词的句子,并且...
这道题,我们需要先通过把单词录入哈希表。然后构造一个可达性DP,dp[i] 代表了 s[0..i] 是否能拆分成 wordsDict 中的单词,再通过可达性 DP 构造一个 prevs 数组记录从某个位置 j 能够构造出的多个单词起点 i 的关系图。最后通过回溯 DFS,从尾部开始向前搜索 prevs 数组,一直遍历到头,得到的 path 一定是一个涵盖 wordsDict 单词的句子,并且...
平衡二叉树这个需要左右子树的深度差小于等于1,dfs解决func isBalanced(root *TreeNode) bool { _, bal...
全排列这题目也是一开始完全没有思路,不知道咋才能把全部的都输出一遍,感觉套for循环也不知道怎么写,后来看到答案直接恍然大悟,这其实是一个经典的回溯题,dfs+状态回溯即可完成。值得注意的是,通过这道题还突然意识到golang的函数传递其实是值传递,实在是太久没有看相关的文章有点忘记了,这里如果res的参数类型改成非指针,就会复制一份切片的结构体过去,一般情况下这不会引发任何问题,但是一旦进...