教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读「模糊坐标」Ambiguous Coordinates是一道典型的「枚举 模拟」类字符串构造题给定一个移除逗号、小数点与空格后得到的数字串S要求还原出所有可能的原始坐标表示。本文以 LogicStack-LeetCode 仓库 中的官方题解为骨架从题目约束推导合法性规则讲解「枚举逗号 枚举小数点」的两层分割框架并给出 Java、C、Python、TypeScript 四种语言的完整可运行实现与复杂度分析。读完本文你将掌握一类「把一段字符串按规则重新切分、去重组合」问题的通用解法套路。题目理解从一串数字还原坐标我们有一些二维坐标如(1, 3)或(2, 0.5)。如果移除所有逗号、小数点和空格会得到一个字符串S例如(123)、(00011)。题目要求返回所有可能的原始字符串列表顺序任意且注意返回的两个数字中间逗号之后都有一个空格。题目给出的约束与合法性规则如下原始的坐标表示法不会存在多余的零因此不会出现类似00、0.0、0.00、1.0、001、00.01或任何用更小的数来表示坐标的形式。一个小数点前至少存在一个数因此也不会出现.1形式的数字。数据范围4 S.length 12且S[0] (、S[S.length - 1] )中间其他元素都是数字。这里的关键约束可以拆成两条硬规则整数形式无小数点不能有前导零001、00非法但单个0是合法的。小数形式有小数点整数部分不能有多余的前导零00、01非法但0合法小数部分不能以0结尾1.0、0.00非法因为末尾的 0 属于多余零。下面看四个示例示例 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 是不被允许的。思路分析两次「分割点枚举」框架由于S本身只是坐标字符串去掉了逗号、小数点和括号还原的过程本质上就是在正确的位置把逗号和小数点重新插回去。本题的解法采用两层枚举第一次分割枚举逗号位置先将原字符串s中的左右括号去掉重新定义s为原字符串的s[1...(n-2)]去掉首尾括号重新定义后的s长度为n。随后枚举逗号的位置idx枚举范围为[0, n - 1)含义是在s[idx]后面追加逗号。此时左边部分字符串为s[0, idx]右边部分字符串为s[idx 1, n - 1]。逗号两侧必须各至少有一个数字所以idx最多枚举到n - 2保证右侧至少剩一个字符。第二次分割枚举小数点位置实现一个搜索函数search(start, end)返回使用字符串s[start...end]能构造出的所有合法数值表示集合。假设入参start和end对应的子串为sub做法是枚举追加小数点的位置idx范围[start, end - 1)含义是在sub[idx]后面追加小数点小数点前面的部分不能包含前导零即整数部分长度大于 1 时首字符不能是0小数点后面的部分不能包含后导零即小数部分末字符不能是0同时记得把不添加小数点的合法整数方案也存入搜索集合长度为 1或首字符不为0时合法。乘法原理合并结果假设左边字符串s[0, idx]的搜索结果为集合A右边字符串s[idx 1, n - 1]的搜索结果为集合B根据「乘法原理」所有实际方案为(x, y)其中x ∈ A、y ∈ B即对两个集合做笛卡尔积并拼装成( x , y )的形式。整个算法的骨架非常清晰去掉首尾括号枚举逗号位置第一层分割对左右两段分别调用search枚举小数点第二层分割将两侧合法数值两两组合成坐标字符串。合法性规则的形式化表达把上面两条规则用代码条件精确表达就是search函数中仅有的两个continue判断情形合法条件非法反例整数无小数点子串长度为 1或首字符不为000、001小数整数部分长度大于 1 时首字符不能为001.2、00.1小数小数部分末字符不能为01.0、0.00、1.20注意0.5这类形式是合法的——整数部分是单个0不违反前导零规则0.01也合法——小数部分01的末字符是1不违反后导零规则。手推示例验证以示例 1 的(123)为例去掉括号后s 123n 3逗号放在idx 0左1→search得[1]右23→ 得[23, 2.3]。组合出(1, 23)、(1, 2.3)。逗号放在idx 1左12→ 得[12, 1.2]右3→ 得[3]。组合出(12, 3)、(1.2, 3)。共得到 4 个结果与示例输出一致。再看示例 2 的(00011)去掉括号后s 00011逗号在idx 0左0→[0]右0011→ 整数0011前导零非法枚举小数点0.011合法整数部分单个0小数部分末字符100.11、001.1整数部分前导零非法 → 得[0.011]。组合出(0, 0.011)。逗号在idx 1、idx 2左侧00、000均无法构造合法数值无结果。逗号在idx 3左0001→ 整数非法枚举小数点仅0.001合法右1→[1]。组合出(0.001, 1)。最终得到[(0.001, 1), (0, 0.011)]与示例 2 吻合且排除了00、0001、0.0、00.01等非法形式。代码实现Javaclass Solution { String s; public ListString ambiguousCoordinates(String _s) { s _s.substring(1, _s.length() - 1); int n s.length(); ListString ans new ArrayList(); for (int i 0; i n - 1; i) { // 枚举逗号在 i 的后面追加逗号 ListString a search(0, i), b search(i 1, n - 1); for (String x : a) { for (String y : b) { ans.add(( x , y )); } } } return ans; } ListString search(int start, int end) { ListString ans new ArrayList(); if (start end || s.charAt(start) ! 0) ans.add(s.substring(start, end 1)); for (int i start; i end; i) { // 枚举小数点在 i 后面追加小数点 String a s.substring(start, i 1), b s.substring(i 1, end 1); if (a.length() 1 a.charAt(0) 0) continue; if (b.charAt(b.length() - 1) 0) continue; ans.add(a . b); } return ans; } }Cclass Solution { public: string s; vectorstring ambiguousCoordinates(string _s) { s _s.substr(1, _s.size() - 2); int n s.size(); vectorstring ans; for (int i 0; i n - 1; i) { vectorstring a search(0, i), b search(i 1, n - 1); for (auto x : a) { for (auto y : b) { ans.push_back(( x , y )); } } } return ans; } vectorstring search(int start, int end) { vectorstring ans; if (start end || s[start] ! 0) ans.push_back(s.substr(start, end - start 1)); for (int i start; i end; i) { string a s.substr(start, i - start 1), b s.substr(i 1, end - i); if (a.size() 1 a[0] 0) continue; if (b.back() 0) continue; ans.push_back(a . b); } return ans; } };Pythonclass Solution: def ambiguousCoordinates(self, _s: str) - List[str]: def search(s, start, end): ans [] if start end or s[start] ! 0: ans.append(s[start:end1]) for i in range(start, end): a, b s[start:i1], s[i1:end1] if len(a) 1 and a[0] 0: continue if b[-1] 0: continue ans.append(f{a}.{b}) return ans s _s[1:len(_s)-1] n len(s) ans [] for i in range(n - 1): a, b search(s, 0, i), search(s, i 1, n - 1) for x in a: for y in b: ans.append(f({x}, {y})) return ansTypeScriptfunction ambiguousCoordinates(_s: string): string[] { function search(s: string, start: number, end: number): string[] { const ans new Arraystring() if (start end || s[start] ! 0) ans.push(s.substring(start, end 1)) for (let i start; i end; i) { const a s.substring(start, i 1), b s.substring(i 1, end 1) if (a.length 1 a[0] 0) continue if (b[b.length - 1] 0) continue ans.push(a . b) } return ans } const s _s.substring(1, _s.length - 1) const n s.length const ans new Arraystring() for (let i 0; i n - 1; i) { const a search(s, 0, i), b search(s, i 1, n - 1) for (const x of a) { for (const y of b) { ans.push(( x , y )) } } } return ans }四种语言的实现完全同构主函数负责去括号与枚举逗号search函数负责对子串枚举小数点并做合法性过滤双层for完成笛卡尔积拼接。区别仅在于字符串截取与拼接的语法细节。复杂度分析时间复杂度O(n^3)。其中n是去掉首尾括号后的数字串长度题目限制4 S.length 12故n 10。外层枚举逗号有O(n)种位置对每个逗号位置左右两段各自枚举小数点共O(n)种切法而答案的构造需要对左右两侧的合法表示做两两组合单个子串的合法表示数量与该子串长度同阶因此组合阶段最坏情况为O(n^2)。整体约为O(n^3)。空间复杂度O(n^3)。主要开销是答案列表本身最坏情况下合法坐标的数量级为O(n^3)search函数内部仅使用与答案规模同阶的临时集合未使用额外递归栈或大型辅助结构。由于n最多只有 10O(n^3)的上界在实际数据下非常轻松这也正是该题采用朴素枚举即可通过的原因。仓库中的归类与延伸阅读本题在 LogicStack-LeetCode 仓库 中被归类为「模拟」类目收录于 Index/模拟.md推荐指数为四星。该类目还收录了大量同类「枚举 模拟」的字符串构造题如 65. 有效数字、166. 分数到小数 等它们与本题共享同一套方法论先把问题拆解为若干「可枚举的分割点」再对每一段做独立的合法性判定最后按规则组合。本题的完整题解源码位于 LeetCode/811-820/816. 模糊坐标中等.md可以直接对照阅读与调试。掌握「两层分割点枚举 合法性过滤 乘法原理组合」这一套路后遇到类似的字符串还原、区间切分、括号配对类题目都可以举一反三。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐旧盒子装新系统B860AV3.2-M 刷 Armbian 实测手册旧盒子装新系统B860AV3.2 M 刷 Armbian 实测手册 这篇手册讲的是把 ZXV10 B860AV3.2 M 这款 S905L3 电视盒子做 Ar嵌入式开发工具构建工具操作系统NetAlertX Net Tools API 完全指南Bearer Token 认证下的七类网络诊断端点NetAlertX Net Tools API 完全指南Bearer Token 认证下的七类网络诊断端点 NetAlertX 的 Net Tools API教程文档LeetCode 816 模糊坐标题解以笛卡尔积优化回溯剪枝的字符串枚举实战LeetCode 816 模糊坐标题解以笛卡尔积优化回溯剪枝的字符串枚举实战 导读 本文围绕 LeetCode 816「模糊坐标Ambiguous Coor文档教程知识库上一篇OOTDiffusion 虚拟试穿完整部署指南:从环境配置到半身全身试穿下一篇Sendwithus开源电子邮件模板项目从模板设计到社区贡献的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考