816. 模糊坐标 : 简单枚举运用题

Love The Way You Lie 2023-10-03 21:22 19阅读 0赞

### 题目描述 ###

这是 LeetCode 上的 **[816. 模糊坐标][816.]** ，难度为 **中等**。

Tag : 「枚举」、「模拟」

我们有一些二维坐标，如 `"(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<=124 <= S.length <= 124<=S.length<=12
 *  `S[0] = "(", S[S.length - 1] = ")"`, 且字符串 `S` 中的其他元素都是数字。

### 枚举 ###

我们先将原字符串 `s` 中的左右括号去掉，重新定义 `s` 为原字符串 s\[1...(n−2)\]s\[1...(n - 2)\]s\[1...(n−2)\]，重新定义后的 `s` 长度为 `n`。

随后枚举逗号的位置 `idx`，枚举范围为 \[0,n−1)\[0, n - 1)\[0,n−1)，含义为在 s\[idx\]s\[idx\]s\[idx\] 后面追加逗号。

此时左边部分字符串为 s\[0,idx\]s\[0, idx\]s\[0,idx\]，右边部分字符串为 s\[idx+1,n−1\]s\[idx + 1, n - 1\]s\[idx+1,n−1\]。

实现一个搜索函数 `List<String> search(int start, int end)`，该函数返回使用字符串 s\[start...end\]s\[start...end\]s\[start...end\] 构造的具体数值集合。

假设左边字符串 s\[0,idx\]s\[0, idx\]s\[0,idx\] 搜索结果为 `A`，右边字符串 s\[idx+1,n−1\]s\[idx + 1, n - 1\]s\[idx+1,n−1\] 搜索结果为 `B`，根据「乘法原理」，可知所有实际方案为 `(x, y)` 其中 x∈Ax \\in Ax∈A，y∈By \\in By∈B。

考虑如何实现 `search` 函数（假设入参函数 `start` 和 `end` 对应的子串为 `sub`）：枚举字符串追加小数点的位置 `idx`，枚举范围为 \[start,end−1)\[start, end - 1)\[start,end−1)，含义为在 sub\[idx\]sub\[idx\]sub\[idx\] 后面追加小数点。小数点前面的部分不能包含前导零，小数点后面的部分不能包含后导零。注意记得把不添加小数点的合法方案也存入搜索集合。

Java 代码：

class Solution {
        String s;
        public List<String> ambiguousCoordinates(String _s) {
            s = _s.substring(1, _s.length() - 1);
            int n = s.length();
            List<String> ans = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) { // 枚举逗号：在 i 的后面追加逗号
                List<String> a = search(0, i), b = search(i + 1, n - 1);
                for (String x : a) {
                    for (String y : b) {
                        ans.add("(" + x + ", " + y + ")");
                    }
                }
            }
            return ans;
        }
        List<String> search(int start, int end) {
            List<String> ans = new ArrayList<>();
            if (start == end || s.charAt(start) != '0') ans.add(s.substring(start, end + 1));
            for (int i = start; i < end; i++) { // 枚举小数点：在 i 后面追加小数点
                String a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1);
                if (a.length() > 1 && a.charAt(0) == '0') continue;
                if (b.charAt(b.length() - 1) == '0') continue;
                ans.add(a + "." + b);
            }
            return ans;
        }
    }
    复制代码

TypeScript 代码：

Python 代码：

class Solution:
        def ambiguousCoordinates(self, _s: str) -> List[str]:
            def search(s, start, end):
                ans = []
                if start == end or s[start] != '0':
                    ans.append(s[start:end+1])
                for i in range(start, end):
                    a, b = s[start:i+1], s[i+1:end+1]
                    if len(a) > 1 and a[0] == '0':
                        continue
                    if b[-1] == '0':
                        continue
                    ans.append(f'{a}.{b}')
                return ans
            s = _s[1:len(_s)-1]
            n = len(s)
            ans = []
            for i in range(n - 1):
                a, b = search(s, 0, i), search(s, i + 1, n - 1)
                for x in a:
                    for y in b:
                        ans.append(f'({x}, {y})')
            return ans
    复制代码

*  时间复杂度：O(n3)O(n^3)O(n3)
 *  空间复杂度：O(n3)O(n^3)O(n3)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.816` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

[816.]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fambiguous-coordinates%2Fsolution%2Fby-ac_oier-sbxl%2F