# 0816. 模糊坐标 ### 题目地址（816. 模糊坐标） ### 题目描述 ``` 我们有一些二维坐标，如 "(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 题解仓库： 。 目前已经 37K star 啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://p.ipic.vip/066kzt.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/816.ambiguous-coordinates.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.