LeetCode刷题之路 模糊坐标

模糊坐标【中等】

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

解题思路

首先利用切片将括号里的数字提取出来，然后进行数字的拆分,在拆分的数字里添加加小数点，添加小数点时要考虑的就是对首位或末尾为0数字的相关处理，不是首位或末尾为0的数字就直接进行迭代添加小数点即可（当然不要忘了返回不用添加小数点的数字）。最后将拆分添加小数点完成的数字列表通过itertools.product函数进行笛卡尔积的计算，转换成相应格式添加到返回的列表中。示例代码如下：

#摘自本题评论，笔者的代码有点麻烦，就不献丑了。
class Solution:
    def ambiguousCoordinates(self, S):
            """
            :type S: str
            :rtype: List[str]
            """
            S = S[1:-1]
            res = []
            # 加小数点
            def f(S):
                if not S or (len(S) > 1 and S[0] == "0" and S[-1] == "0"):
                    return []
                if S == "0":
                    return [S[0]]
                if S[0] == "0" and len(S) > 1:
                    return [S[0]+ "." + S[1:]]
                if S[-1] =="0" and len(S)  > 1:
                    return [S]
                return [S] +  [S[:i] + "." + S[i:] for i in range(1, len(S))]
            # 拆数字
            for i in range(1,len(S)):
                for x,y in itertools.product(f(S[:i]), f(S[i:])):
                    res.append("(%s, %s)"%(x,y))
            return res

附：

itertools.product(*iterables[, repeat])
返回一个迭代器，生成表示item1，item2等中的项目的笛卡尔积的元组，repeat是一个关键字参数，指定重复生成序列的次数。示例代码如下：

import itertools 

list1 = [1,2,3]
list2 = ['a','b','c']

for i in itertools.product(list1,list2):
    print(i)
    
print('-' * 30)

for i in itertools.product(list1,repeat=2):
    print(i)
    
print('-' * 30)
    
for i in itertools.product(range(4,7),repeat=2):
    print(i) 
    
'''
(1, 'a')
(1, 'b')
(1, 'c')
(2, 'a')
(2, 'b')
(2, 'c')
(3, 'a')
(3, 'b')
(3, 'c')
------------------------------
(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)
------------------------------
(4, 4)
(4, 5)
(4, 6)
(5, 4)
(5, 5)
(5, 6)
(6, 4)
(6, 5)
(6, 6)
'''

itertools模块能够返回多种迭代器，包括无限迭代器，处理输入序列迭代器，组合生成器等等，感兴趣的朋友可以参考：https://www.jb51.net/article/65782.htm