LC 816. 模糊坐标

题目描述

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

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串 S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于 "00", "0.0", "0.00", "1.0", "001", "00.01" 或一些其他更小的数来表示坐标。

此外，一个小数点前至少存在一个数，所以也不会出现 “.1” 形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例 1:

1
2
3
输入: "(123)"

输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

示例 2:
1
2
3
4
5
6
输入: "(00011)"

输出:  ["(0.001, 1)", "(0, 0.011)"]

解释: 
0.0, 00, 0001 或 00.01 是不被允许的。

示例 3:
1
2
3
输入: "(0123)"

输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

示例 4:
1
2
3
4
5
6
输入: "(100)"

输出: [(10, 0)]

解释: 
1.0 是不被允许的。

提示:

  • $4 <= S.length <= 12$
  • S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。

枚举

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

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

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

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

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

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

Java 代码：

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
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;
    }
}

C++ 代码：
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
class Solution {
public:
    string s;
    vector<string> ambiguousCoordinates(string _s) {
        s = _s.substr(1, _s.size() - 2);
        int n = s.size();
        vector<string> ans;
        for (int i = 0; i < n - 1; i++) {
            vector<string> a = search(0, i), b = search(i + 1, n - 1);
            for (auto &x : a) {
                for (auto &y : b) {
                    ans.push_back("(" + x + ", " + y + ")");
                }
            }
        }
        return ans;
    }
    vector<string> search(int start, int end) {
        vector<string> ans;
        if (start == end || s[start] != '0') ans.push_back(s.substr(start, end - start + 1));
        for (int i = start; i < end; i++) {
            string a = s.substr(start, i - start + 1), b = s.substr(i + 1, end - i);
            if (a.size() > 1 && a[0] == '0') continue;
            if (b.back() == '0') continue;
            ans.push_back(a + "." + b);
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

TypeScript 代码：
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
function ambiguousCoordinates(_s: string): string[] {
    function search(s: string, start: number, end: number): string[] {
        const ans = new Array<string>()
        if (start == end || s[start] != '0') ans.push(s.substring(start, end + 1))
        for (let i = start; i < end; i++) {
            const a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1)
            if (a.length > 1 && a[0] == '0') continue
            if (b[b.length - 1] == '0') continue
            ans.push(a + '.' + b)
        }
        return ans
    }
    const s = _s.substring(1, _s.length - 1)
    const n = s.length
    const ans = new Array<string>()
    for (let i = 0; i < n - 1; i++) {
        const a = search(s, 0, i), b = search(s, i + 1, n - 1)
        for (const x of a) {
            for (const y of b) {
                ans.push('(' + x + ', ' + y + ')')
            }
        }
    }
    return ans
}

  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^3)$

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。