原文链接: https://leetcode-cn.com/problems/ambiguous-coordinates

英文原文

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces and ended up with the string s.

• For example, "(1, 3)" becomes s = "(13)" and "(2, 0.5)" becomes s = "(205)".

Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)

 

Example 1:

Input: s = "(123)"
Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]

Example 2:

Input: s = "(0123)"
Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]
Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3:

Input: s = "(00011)"
Output: ["(0, 0.011)","(0.001, 1)"]

Example 4:

Input: s = "(100)"
Output: ["(10, 0)"]
Explanation: 1.0 is not allowed.

 

Constraints:

• 4 <= s.length <= 12
• s[0] == '(' and s[s.length - 1] == ')'.
• The rest of s are digits.

中文题目

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

 

通过代码

官方题解

枚举：

我们首先把这个二维坐标分成两部分，前一部分表示 x 坐标，后一部分表示 y 坐标。例如当给出的二维坐标为 (1234) 时，我们可以把它分成 1, 234，12, 34 和 123, 4 三种情况。随后对于每一部分，我们再考虑是否可以添加小数点以及在哪里添加小数点。例如，对于 123，合法的坐标有 1.23，12.3 和 123。

在处理每一部分时，我们需要将出现多余 0 的不合法的坐标去除。如果我们不添加小数点，那么这个坐标不能有前导 0；如果我们在某个位置添加小数点，那么整数部分不能有前导 0，小数部分的末尾也不能有 0。

[sol1]
class Solution { //aw
    public List<String> ambiguousCoordinates(String S) {
        List<String> ans = new ArrayList();
        for (int i = 2; i < S.length()-1; ++i)
            for (String left: make(S, 1, i))
                for (String right: make(S, i, S.length()-1))
                    ans.add("(" + left + ", " + right + ")");
        return ans;
    }

    public List<String> make(String S, int i, int j) {
        // Make on S.substring(i, j)
        List<String> ans = new ArrayList();
        for (int d = 1; d <= j-i; ++d) {
            String left = S.substring(i, i+d);
            String right = S.substring(i+d, j);
            if ((!left.startsWith("0") || left.equals("0"))
                    && !right.endsWith("0"))
                ans.add(left + (d < j-i ? "." : "") + right);
        }
        return ans;
    }
}

[sol1]
class Solution(object):
    def ambiguousCoordinates(self, S):
        def make(frag):
            N = len(frag)
            for d in xrange(1, N+1):
                left = frag[:d]
                right = frag[d:]
                if ((not left.startswith('0') or left == '0')
                        and (not right.endswith('0'))):
                    yield left + ('.' if d != N else '') + right

        S = S[1:-1]
        return ["({}, {})".format(*cand)
                for i in xrange(1, len(S))
                for cand in itertools.product(make(S[:i]), make(S[i:]))]

复杂度分析

• 时间复杂度：$O(N^3)$，其中 $N$ 是字符串 S 的长度。

• 空间复杂度：$O(N^3)$，用来存储所有合法的情况。

统计信息

通过次数	提交次数	AC比率
3754	7318	51.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言