feat: 回溯，$140 $ 816

lucifer · lucifer · commit d541a379aac1 · 2020-11-02T15:34:23.000+08:00
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -168,6 +168,7 @@
     * [0718. 最长重复子数组](problems/718.maximum-length-of-repeated-subarray.md)
     * [0754. 到达终点数字](problems/754.reach-a-number.md)
     * [0785. 判断二分图](problems/785.is-graph-bipartite.md)
+    * [0816.ambiguous-coordinates](problems/816.ambiguous-coordinates.md)
     * [0820. 单词的压缩编码](problems/820.short-encoding-of-words.md)
     * [0875. 爱吃香蕉的珂珂](problems/875.koko-eating-bananas.md)
     * [0877. 石子游戏](problems/877.stone-game.md)
@@ -209,6 +210,7 @@
     * [0085. 最大矩形](problems/85.maximal-rectangle.md)
     * [0124. 二叉树中的最大路径和](problems/124.binary-tree-maximum-path-sum.md)
     * [0128. 最长连续序列](problems/128.longest-consecutive-sequence.md)
+    * [0140. 单词拆分 II](problems/140.word-break-ii.md)
     * [0145. 二叉树的后序遍历](problems/145.binary-tree-postorder-traversal.md)
     * [0212. 单词搜索 II](problems/212.word-search-ii.md)
     * [0239. 滑动窗口最大值](problems/239.sliding-window-maximum.md)
diff --git a/collections/hard.md b/collections/hard.md
@@ -35,6 +35,7 @@
 - [0085. 最大矩形](../problems/85.maximal-rectangle.md)
 - [0124. 二叉树中的最大路径和](../problems/124.binary-tree-maximum-path-sum.md)
 - [0128. 最长连续序列](../problems/128.longest-consecutive-sequence.md)
+- [0140. 单词拆分 II](problems/140.word-break-ii.md) 🆕
 - [0145. 二叉树的后序遍历](../problems/145.binary-tree-postorder-traversal.md)
 - [0212. 单词搜索 II](../problems/212.word-search-ii.md)
 - [0239. 滑动窗口最大值](../problems/239.sliding-window-maximum.md)
diff --git a/collections/medium.md b/collections/medium.md
@@ -91,6 +91,7 @@
 - [0718. 最长重复子数组](../problems/718.maximum-length-of-repeated-subarray.md)
 - [0754. 到达终点数字](../problems/754.reach-a-number.md)
 - [0785. 判断二分图](../problems/785.is-graph-bipartite.md)
+- [0816.ambiguous-coordinates](../problems/816.ambiguous-coordinates.md) 🆕
 - [0820. 单词的压缩编码](../problems/820.short-encoding-of-words.md)
 - [0875. 爱吃香蕉的珂珂](../problems/875.koko-eating-bananas.md)
 - [0877. 石子游戏](../problems/877.stone-game.md)
diff --git a/problems/140.word-break-ii.md b/problems/140.word-break-ii.md
@@ -0,0 +1,172 @@
+## 题目地址（140. 单词拆分 II）
+
+https://leetcode-cn.com/problems/word-break-ii/
+
+## 题目描述
+
+```
+给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
+
+说明：
+
+分隔时可以重复使用字典中的单词。
+你可以假设字典中没有重复的单词。
+示例 1：
+
+输入:
+s = "catsanddog"
+wordDict = ["cat", "cats", "and", "sand", "dog"]
+输出:
+[
+  "cats and dog",
+  "cat sand dog"
+]
+示例 2：
+
+输入:
+s = "pineapplepenapple"
+wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
+输出:
+[
+  "pine apple pen apple",
+  "pineapple pen apple",
+  "pine applepen apple"
+]
+解释: 注意你可以重复使用字典中的单词。
+示例 3：
+
+输入:
+s = "catsandog"
+wordDict = ["cats", "dog", "sand", "and", "cat"]
+输出:
+[]
+
+```
+
+微软有一道题和这个一样 [题目地址](https://github.com/azl397985856/fe-interview/issues/153) 一样，感兴趣的可以看看完整面经。
+
+## 前置知识
+
+- 回溯
+- 笛卡尔积
+
+## 公司
+
+- 暂无
+
+## 暴力回溯
+
+### 思路
+
+实际上这道题就是暴力回溯就好了， 代码也比较简单。
+
+### 代码
+
+代码支持：Python3
+
+Python3 Code:
+
+```py
+class Solution:
+    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
+        ans = []
+        n = len(s)
+
+        def backtrack(temp, start):
+            if start == n: ans.append(temp[1:])
+            for i in range(start, n):
+                if s[start:i + 1] in wordDict:
+                    backtrack(temp + " " + s[start:i + 1], i + 1)
+        backtrack('', 0)
+        return ans
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(2^N)$
+- 空间复杂度：$O(2^N)$
+
+## 笛卡尔积优化
+
+### 思路
+
+上面的代码会超时，测试用例会挂在如下：
+
+```js
+"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"[
+  ("a",
+  "aa",
+  "aaa",
+  "aaaa",
+  "aaaaa",
+  "aaaaaa",
+  "aaaaaaa",
+  "aaaaaaaa",
+  "aaaaaaaaa",
+  "aaaaaaaaaa")
+];
+```
+
+也就是说 s 的长度是 151， 这超时也就能够理解了，但是力扣的题目描述没有给数据范围。 **如果是真实的面试， 一定先问清楚数据范围**。
+
+接下来，我们考虑优化。
+
+通过观察发现， 对于一个字符串 s，比如 "helloworldhi" 而言，假设 dict 为：
+
+```js
+{
+  hi: true,
+  h: true,
+  i: true,
+  world: true,
+  hello: true,
+
+}
+```
+
+1. 当我们 DFS 探到底部的时候，也就是触及到 hi。我们就知道了，s[-2:] 可能组成的所有可能就是 ['hi', 'h', 'i']
+2. 当我们 DFS 探到 worldhi 的时候。我们就知道了，s[-7:] 可能组成的所有可能就是 ['worldhi', 'worldh', 'worldi']
+3. 如上只是一个分支的情况，如果有多个分支，那么步骤 1 就会被重复计算。
+
+我们也不难看出， 当我们 DFS 探到 worldhi 的时候，其可能的结果就是探测到的单词和上一步的所有可能的笛卡尔积。
+
+因此一种优化思路就是将回溯的结果通过返回值的形式传递给父级函数，父级函数通过笛卡尔积构造 ans 即可。而这实际上和上面的解法复杂度是一样的， 但是经过这样的改造，我们就可以使用记忆化技巧减少重复计算了。因此理论上， 我们不存在**回溯**过程了。 因此时间复杂度就是所有的组合，即一次遍历以及内部的笛卡尔积，也就是 $O(N ^ 2)$。
+
+### 代码
+
+代码支持：Python3
+
+Python3 Code:
+
+```py
+class Solution:
+    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
+        n = len(s)
+        @lru_cache(None)
+        def backtrack(start):
+            ans = []
+            if start == n:
+                ans.append('')
+            for i in range(start, n):
+                if s[start:i + 1] in wordDict:
+                    if start == 0: temp = s[start:i + 1]
+                    else: temp = " " + s[start:i + 1]
+                    ps = backtrack(i + 1)
+                    for p in ps:
+                        ans.append(temp + p)
+            return ans
+        return backtrack(0)
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N^2)$
+- 空间复杂度：$O(N^2)$
+
+这种记忆化递归的方式和 DP 思想一模一样， 大家可以将其改造为 DP，这个留给大家来完成。
+
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/problems/816.ambiguous-coordinates.md b/problems/816.ambiguous-coordinates.md
@@ -0,0 +1,142 @@
+## 题目地址（816. 模糊坐标）
+
+https://leetcode-cn.com/problems/ambiguous-coordinates
+
+## 题目描述
+
+```
+我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。
+
+原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。
+
+最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。
+
+ 
+
+示例 1:
+输入: "(123)"
+输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
+示例 2:
+输入: "(00011)"
+输出:  ["(0.001, 1)", "(0, 0.011)"]
+解释:
+0.0, 00, 0001 或 00.01 是不被允许的。
+示例 3:
+输入: "(0123)"
+输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
+示例 4:
+输入: "(100)"
+输出: [(10, 0)]
+解释:
+1.0 是不被允许的。
+ 
+
+提示:
+
+4 <= S.length <= 12.
+S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。
+
+```
+
+## 前置知识
+
+- 回溯
+- 笛卡尔积
+
+## 公司
+
+- 暂无
+
+## 思路
+
+这个也是一个明显的笛卡尔积的题目。
+
+我们先将题目简化一下，不考虑题目给的那些限制， 只要将其分割成逗号分割的两部分即可，不用考虑是否是有效的（比如不能是 001 等）。
+
+那么代码大概是：
+
+Python3 Code:
+
+```python
+class Solution:
+
+    def subset(self, s: str):
+        ans = []
+        for i in range(1, len(s)):
+            ans.append(s[:i] + "." + s[i:])
+        ans.append(s)
+        return ans
+
+    def ambiguousCoordinates(self, s: str) -> List[str]:
+        ans = []
+        s = s[1:-1]
+        for i in range(1, len(s)):
+            x = self.subset(s[:i])
+            y = self.subset(s[i:])
+            for i in x:
+                for j in y:
+                    ans.append('(' + i + ', ' + j + ')')
+        return ans
+
+```
+
+我简单解释一下上面代码的意思。
+
+- 将字符串分割成两部分， 其所有的可能性无非就是枚举切割点，这里使用了一个 for 循环。
+- subset(s) 的功能是在 s 的第 0 位后，第一位后，第 n - 2 位后插入一个小数点 "."，其实就是构造一个有效的数字而已。
+- 因此 x 和 y 就是分割形成的两部分的有效分割集合，**答案自然就是 x 和 y 的笛卡尔积**。
+
+如果上面的代码你会了，这道题无非就是增加几个约束， 我们剪几个不合法的枝即可。具体代码见下方代码区，可以看出，代码仅仅是多了几个 if 判断而已。
+
+上面的目标很常见，请**务必掌握**。
+
+## 关键点
+
+- 笛卡尔积优化
+
+## 代码
+
+代码支持：Python3
+
+```python
+class Solution:
+    # "123" => ["1.23", "12.3", "123"]
+    def subset(self, s: str):
+        ans = []
+
+        #  带小数点的
+        for i in range(1, len(s)):
+            # 不允许 00.111， 0.0，01.1，1.0
+            if s[0] == '0' and i > 1:
+                continue
+            if s[-1] == '0':
+                continue
+            ans.append(s[:i] + "." + s[i:])
+        # 不带小数点的（不允许 001）
+        if s == '0' or not s.startswith('0'):
+            ans.append(s)
+        return ans
+
+    def ambiguousCoordinates(self, s: str) -> List[str]:
+        ans = []
+        s = s[1:-1]
+        for i in range(1, len(s)):
+            x = self.subset(s[:i])
+            y = self.subset(s[i:])
+            for i in x:
+                for j in y:
+                    ans.append('(' + i + ', ' + j + ')')
+        return ans
+
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N^3)$
+- 空间复杂度：$O(N^2)$
+
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/thinkings/backtrack.md b/thinkings/backtrack.md
