LeetCode 816. 模糊坐标

1. 问题描述：

给定一个字符串 S 表示一组坐标，其中括号 () 包围了一个去除逗号、小数点和空格的数字。我们需要返回所有可能的原始坐标表示形式的列表，满足以下条件：

有效坐标格式为 (X, Y)，其中 X 和 Y 是有效数字。

数字要求：

1. 无多余前导零，如 "01", "00.1" 是无效的。
2. 小数点之前必须至少有一个数字，如 ".1" 无效。
3. 结果中不包含多余的小数点，如 "1.0" 是无效的。
4. 结果列表可以是任意顺序。

输入格式：

输入一个字符串 S，其中 S 的第一个字符是 (，最后一个字符是 )，中间是去掉逗号、小数点和空格的数字。

输出格式：

返回一个包含所有有效原始坐标表示的列表。

示例输入与输出：

示例 1： 输入：
(123)

输出：
["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

示例 2： 输入：
(00011)

输出：
["(0.001, 1)", "(0, 0.011)"]

解释：无效的数字如 "00", "0001" 被排除。

示例 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"。

2. 思路解析

字符串分割：

将字符串去掉括号，然后分成两部分 X 和 Y，分别表示坐标的两部分。

生成有效数字：

对每个部分，分别生成所有有效的整数和小数形式。

• 有效的整数：不包含前导零，除非数字是 0 本身。
• 有效的小数：必须满足：
  • 小数点前至少有一个数字。
  • 小数点后的数字不以 0 结尾。

组合结果：

将 X 和 Y 的所有有效形式进行两两组合，形成有效的坐标 (X, Y)。

3. 代码

def ambiguousCoordinates(S):
    # 生成所有有效数字的形式
    def valid_numbers(s):
        results = []
        # 整数形式（排除前导零）
        if s[0] != '0' or s == "0":
            results.append(s)
        # 小数形式（排除不合法的小数）
        for i in range(1, len(s)):
            left, right = s[:i], s[i:]
            if (left == "0" or left[0] != '0') and right[-1] != '0':
                results.append(left + "." + right)
        return results

    S = S[1:-1]  # 去掉括号
    n = len(S)
    results = []

    # 分割字符串成两部分，并生成合法坐标
    for i in range(1, n):
        left_part, right_part = S[:i], S[i:]
        left_numbers = valid_numbers(left_part)
        right_numbers = valid_numbers(right_part)

        # 组合两个部分
        for left in left_numbers:
            for right in right_numbers:
                results.append(f"({left}, {right})")

    return results

# 示例测试
print(ambiguousCoordinates("(123)"))    # 输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
print(ambiguousCoordinates("(00011)"))  # 输出: ["(0.001, 1)", "(0, 0.011)"]
print(ambiguousCoordinates("(0123)"))   # 输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
print(ambiguousCoordinates("(100)"))    # 输出: ["(10, 0)"]