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 = 1point = 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为Falseelse :if string != str(int(string)):li.remove(ch)flag = False # 如果移除了ch,flag为Falsereturn flagnewtemplist = 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

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

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