我们有一些二维坐标，如 "(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中的其他元素都是数字。
暴力模拟。
把 s 按照不同长度去做 x, y 两部分的拆分。
将拆分后的 x, y，分别检查是否满足以下条件：
- 左半部分开头不能是 0（除非是 0 本身）
- 右半部分不能以 0 为结尾
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 ansclass 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);
// 左半部分开头不能是0（除非是0本身）
// 右半部分不能以0为结尾
boolean valid = ("0".equals(left) || !left.startsWith("0")) && !right.endsWith("0");
if (valid) {
res.add(left + (k < j - i ? "." : "") + right);
}
}
return res;
}
}