Leetcode 816. 模糊坐标

Leetcode 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 中的其他元素都是数字。

我的想法：
1.遍历 s ，先给 s 加逗号，加入到列表中；
2.遍历加好逗号的列表，给逗号左边的数字加上小数点，过滤掉不符合的情况，加入到列表中；
3.遍历逗号左边加好小数点的数组，给逗号右边的数字加上小数点，过滤掉不符合的情况，加入到列表中；
4.遍历逗号左边右边都加好小数点的数组，设置一个判断函数，过滤掉不符合的情况，加入到新列表中；
5.输出新列表。

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        templist = list()
        returnlist = list()
        totallist = list()
        slen = len(s)
        for i in range(2,slen-1): # 加逗号
            slist = list(s)
            slist.insert(i,",")
            temp = "".join(slist)
            templist.append(temp)
            returnlist.append(temp)
        
        for ch in templist: # 给逗号左边的数字加小数点
            ch = list(ch)
            left = 1
            point = ch.index(",")
            if point - left > 1:
                for i in range(left+1,point):
                    temp = ch[:]
                    temp.insert(i, ".")
                    temp = "".join(temp)
                    if not temp.startswith("(00") and not temp[:point+1].endswith("00"): # 过滤掉以00开头的 和 小数点前有00的
                        returnlist.append(temp)
        templist = returnlist[:]
        # print(returnlist)
        for ch in templist: # 给逗号右边的的数字加小数点
            if ch.startswith("(00"): # 过滤掉以00开头的
                returnlist.remove(ch)
                continue 
            ch = list(ch)
            right = len(ch) - 2 # 右边的括号
            point = ch.index(",")
            if right - point >= 1:
                for i in range(point+2,right+1):
                    temp = ch[:]
                    temp.insert(i, ".")
                    temp = "".join(temp)
                    if not temp[point+1:i].startswith("00") : # 过滤掉小数点前有00的
                        returnlist.append(temp)
        # print(returnlist)
        def panduan(ch,li:list,string:str): # 设置一个判断函数，过滤掉最后一部分
            flag = True # 使用flag以防ch不在li列表中
            if "." in string:
                if string != str(float(string)) or string.endswith(".0"): # 过滤掉类似 01.2 和 0.0 的情况
                    if not "e" in str(float(string)): # float(0.00001) 为 1e-05 ，过滤掉科学计数法情况
                        li.remove(ch)
                        flag = False # 如果移除了ch,flag为False
            else :
                if string != str(int(string)):
                    li.remove(ch)
                    flag = False # 如果移除了ch,flag为False
            return flag
        newtemplist = returnlist[:]
        for ch in newtemplist:
            right = len(ch) - 2 # 右边的括号
            left = 1 # 左边的括号
            point = ch.index(",") # 找到逗号的位置
            templeft = ch[left:point] # 逗号左边的数字
            tempright = ch[point+1:right+1] # 逗号右边的数字
            if panduan(ch,returnlist,templeft):
                panduan(ch,returnlist,tempright)
        for ch in returnlist:
            ch = ch.replace(",", ", ") # 将逗号后面加空格
            totallist.append(ch)
        return totallist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

没想到没超时，时间复杂度击败了5.88%

看下其他人的题解：
官方题解-枚举
【宫水三叶】简单枚举运用题
ylb-暴力模拟