816. Ambiguous Coordinates

Problem

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.)

https://leetcode.com/problems/ambiguous-coordinates/

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)"]

Constraints:

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

Test Cases

1
2

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ("(123)", ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]),
    ("(0123)", ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]),
    ("(00011)", ["(0, 0.011)","(0.001, 1)"]),

    ("(100)", ["(10, 0)"]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
    assert sorted(sol.ambiguousCoordinates(s)) == sorted(expected)

Thoughts

把 s 两头的括号去掉，剩下都是 digits，设 digits 的个数为 n。可以尝试在所有的位置把 s 分成左右两半，每半至少包含一个 digit。枚举每一半可以构造的有效的数值（有可能一个都没有），左右两半的可行数值数组取笛卡尔积可以得到所有可行的组合。

对于一个由若干个 digits 构成的字符串，看它可以构造出哪些合法的数值。

首先如果只有一个 digit，那么只能构成一个一位整数。

否则如果不以 '0' 开头，那么整体可以构成一个整数。然后看可以构成的小数有哪些。

如果末尾是 '0'，就无法构成任何有效的小数数值。否则如果以 '0' 开头，那么只能构成 0.xxx 这样的唯一一个小数。其他情况下，都可以给任意中间位置插入小数点构成一个小数，都是有效的。

时间复杂度 O(n²)。

Code

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

from itertools import product
from typing import Iterable


class Solution:
    def ambiguousCoordinates(self, s: str) -> list[str]:
        def numbers(l: int, r: int) -> Iterable[str]:
            """Enumerate all possible numbers for substring s[l:r]"""
            if r == l + 1:
                yield s[l] # The single-digit integer.
                return

            if s[l] != '0':
                yield s[l:r] # The multi-digits integer.

            if s[r-1] == '0':
                return # Tailing-zero is not allowed when decimal point exists.

            if s[l] == '0':
                yield f'0.{s[l+1:r]}' # Leading-zero is only allowed for `0.x`.
            else:
                yield from (f'{s[l:i]}.{s[i:r]}' for i in range(l + 1, r))

        n = len(s)
        return [*(f'({a}, {b})' for i in range (2, n-1) for a, b in product(numbers(1, i), numbers(i, n-1)))]

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章