MediumNo. 0816
Ambiguous Coordinates — LeetCode 816 Python Solution
- Pattern
- Backtracking
- Topics
- String, Backtracking, Enumeration
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- s = "(123)"
- Output
- ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]
Python solution
class Solution:
def ambiguousCoordinates(self, s: str) -> List[str]:
def f(i, j):
res = []
for k in range(1, j - i + 1):
l, r = s[i : i + k], s[i + k : j]
ok = (l == '0' or not l.startswith('0')) and not r.endswith('0')
if ok:
res.append(l + ('.' if k < j - i else '') + r)
return res
n = len(s)
return [
f'({x}, {y})' for i in range(2, n - 1) for x in f(1, i) for y in f(i, n - 1)
]Complexity
- Time
- Exponential (worst case)
- Space · auxiliary
- O(depth)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 816. Ambiguous Coordinates is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0949 | Largest Time for Given Digits | Medium |
| 1849 | Splitting a String Into Descending Consecutive Values | Medium |
| 0079 | Word Search | Medium |
| 0093 | Restore IP Addresses | Medium |
| 0212 | Word Search II | Hard |
| 0257 | Binary Tree Paths | Easy |
Frequently asked questions
- How hard is LeetCode 816. Ambiguous Coordinates?
LeetCode 816. Ambiguous Coordinates is rated Medium on LeetCode.
- What topics does LeetCode 816. Ambiguous Coordinates cover?
LeetCode 816. Ambiguous Coordinates is tagged String, Backtracking and Enumeration on LeetCode.