模糊坐标

难度: Medium

我们有一些二维坐标，如 "(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 中的其他元素都是数字。

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        def checkNum(s):
            ans = []
            if len(s) == 1:
                return [s]
            # 首元素为0，但其余元素不可都为0 -> 结合本题无多余0，结尾不可为0
            if s[0] == '0':
                if s[-1] != '0':
                    ans.append(s[0] + '.' + s[1:])

            else: #非0开头
                # 1.0也不可以存在
                for i in range(1, len(s)):
                    if s[-1] != '0':
                        ans.append(s[:i] + '.' + s[i:])
                ans.append(s)
            return ans

        ans = []
        lth = len(s)
        for cutLine in range(2, lth-1): # 2 ~ lth-2
            pre = s[1:cutLine]
            post = s[cutLine : lth - 1]
            pre = checkNum(pre)
            post = checkNum(post)
            if pre and post:
                for i in pre:
                    for j in post:
                        ans.append("(" + i + ", " + j +")")

        return ans

Explain

该题解的思路是先枚举切割点，将原字符串切割成两部分，分别对两部分进行合法性检查。对于每一部分，如果长度为1，直接返回该部分；如果以0开头且结尾不是0，则在首位后插入小数点返回；如果非0开头，则枚举小数点插入位置构造合法的小数。最后将两部分的所有合法组合拼接起来即可得到答案。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        def checkNum(s):
            ans = []
            if len(s) == 1:
                return [s]
            # 首元素为0，但其余元素不可都为0 -> 结合本题无多余0，结尾不可为0
            if s[0] == '0':
                if s[-1] != '0':
                    ans.append(s[0] + '.' + s[1:]) # 在首位后插入小数点
                    
            else: # 非0开头
                # 1.0也不可以存在
                for i in range(1, len(s)): # 枚举小数点插入位置
                    if s[-1] != '0':
                        ans.append(s[:i] + '.' + s[i:])
                ans.append(s) # 不插入小数点的情况
            return ans
        
        ans = []
        lth = len(s)
        for cutLine in range(2, lth-1): # 枚举切割点，2 ~ lth-2
            pre = s[1:cutLine] # 切割点左侧部分
            post = s[cutLine : lth - 1] # 切割点右侧部分
            pre = checkNum(pre) # 检查左侧部分合法性
            post = checkNum(post) # 检查右侧部分合法性
            if pre and post: # 如果左右两部分均合法
                for i in pre:
                    for j in post:
                        ans.append("(" + i + ", " + j +")") # 拼接所有合法组合
        
        return ans

Explore

在数字表示中，以0开头的多位数是不合法的，除非它是小数的形式。因此，当首位为0且数字长度大于1时，我们不能直接使用这个数字除非它形式为0.xxxx。此外，如果一个数字以0开头且结尾也是0，比如'00'、'000'等，则无法形成合法的小数，因此我们只在结尾不是0的情况下，将这种形式转换成小数形式'0.xxxx'。这种特殊处理是为了确保生成的数字是合法的小数或整数。

对于非0开头的数字，我们可以将其视为一个有效的整数，但同时它也可能表示一个小数。为了找出所有可能的表示形式，我们需要在数字的任何位置插入小数点，从而生成不同的小数形式。枚举所有可能的小数点位置可以确保我们不错过任何有效的数字表示。尽管如此，我们仍需要确保小数点后不会全部是0（如1.000是无效的），但在原题解中已考虑这一点，确保最后一位不是0。因此，这种方法可以有效地生成所有合法的数字字符串。

通过checkNum函数，我们确保了每部分数字的合法性。这个函数负责检查并排除那些不符合小数或整数格式的表达方式，例如避免多余的前导0或不恰当的小数点使用。当两部分字符串都通过checkNum函数处理后，我们只组合那些已被验证为合法的数字形式。因此，任何生成的坐标`(x, y)`自然符合题目中对数字格式的所有要求，包括前导零和小数处理。

字符串`s`的格式是`'(12345)'`，其中数字部分位于索引1到`lth-2`。因此，最小的切割点应该是2，这样左侧至少包含一个字符（索引1），右侧至少也包含一个字符（直到`lth-2`）。如果我们从更早的位置开始切割，比如从1开始，那么左侧部分将没有任何字符，这违反了题目要求每个坐标部分至少包含一个数字的规则。