---

0816. 模糊坐标

• 标签：字符串、回溯、枚举
• 难度：中等

题目链接

• 0816. 模糊坐标 - 力扣

题目大意

描述：

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串 $S$。

要求：

返回所有可能的原始字符串到一个列表中。

说明：

• 原始的坐标表示法不会存在多余的零，所以不会出现类似于 "00", "0.0", "0.00", "1.0", "001", "00.01" 或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现 ".1" 形式的数字。
• 最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。
• $4 \le S.length \le 12$。
• S[0] = "(", S[S.length - 1] = ")", 且字符串 S$ 中的其他元素都是数字。

示例：

• 示例 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 是不被允许的。

解题思路

思路 1：枚举 + 字符串处理

这道题要求将去掉括号和逗号的坐标字符串还原为所有可能的原始坐标。

算法步骤：

1. 去掉字符串首尾的括号，得到数字字符串。
2. 枚举逗号的位置，将字符串分为两部分（$x$ 坐标和 $y$ 坐标）。
3. 对于每部分，枚举小数点的位置（包括不加小数点的情况）。
4. 检查生成的数字是否合法：
   • 不能有前导零（除了 "0" 本身）。
   • 小数部分不能有后导零。
5. 组合所有合法的 $x$ 和 $y$ 坐标，生成结果。

辅助函数：生成所有可能的合法数字表示。

思路 1：代码

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        def get_valid_numbers(num_str):
            """生成字符串的所有合法数字表示"""
            n = len(num_str)
            result = []
            
            # 不加小数点
            if n == 1 or num_str[0] != '0':
                result.append(num_str)
            
            # 加小数点
            for i in range(1, n):
                left = num_str[:i]
                right = num_str[i:]
                
                # 检查是否合法：
                # 1. 整数部分不能有前导零（除非是 "0"）
                # 2. 小数部分不能有后导零
                if (left == '0' or left[0] != '0') and right[-1] != '0':
                    result.append(left + '.' + right)
            
            return result
        
        # 去掉首尾括号
        s = s[1:-1]
        n = len(s)
        result = []
        
        # 枚举逗号的位置
        for i in range(1, n):
            x_str = s[:i]
            y_str = s[i:]
            
            # 生成所有可能的 x 和 y 坐标
            x_coords = get_valid_numbers(x_str)
            y_coords = get_valid_numbers(y_str)
            
            # 组合所有可能的坐标
            for x in x_coords:
                for y in y_coords:
                    result.append(f"({x}, {y})")
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是字符串的长度。需要枚举逗号位置 $O(n)$，对于每个位置枚举小数点位置 $O(n)$，生成结果需要 $O(n)$。
• 空间复杂度：$O(n^2)$，需要存储所有可能的坐标表示。