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)"
becomess = "(13)"
and"(2, 0.5)"
becomess = "(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)"]
Constraints:
4 <= s.length <= 12
s[0] == '('
ands[s.length - 1] == ')'
.- The rest of
s
are digits.
class Solution:
def ambiguousCoordinates(self, s: str) -> List[str]:
def convert(i, j):
res = []
for k in range(1, j - i + 1):
left, right = s[i : i + k], s[i + k : j]
valid = (
left == '0' or not left.startswith('0')
) and not right.endswith('0')
if valid:
res.append(left + ('.' if k < j - i else '') + right)
return res
n = len(s)
ans = []
for i in range(2, n - 1):
for x in convert(1, i):
for y in convert(i, n - 1):
ans.append(f'({x}, {y})')
return ans
class Solution {
public List<String> ambiguousCoordinates(String s) {
int n = s.length();
List<String> ans = new ArrayList<>();
for (int i = 2; i < n - 1; ++i) {
for (String x : convert(s, 1, i)) {
for (String y : convert(s, i, n - 1)) {
ans.add(String.format("(%s, %s)", x, y));
}
}
}
return ans;
}
private List<String> convert(String s, int i, int j) {
List<String> res = new ArrayList<>();
for (int k = 1; k <= j - i; ++k) {
String left = s.substring(i, i + k);
String right = s.substring(i + k, j);
boolean valid = ("0".equals(left) || !left.startsWith("0")) && !right.endsWith("0");
if (valid) {
res.add(left + (k < j - i ? "." : "") + right);
}
}
return res;
}
}