题目描述
我们有一些二维坐标，如 "(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$ 按照小数点的位置分成左右两部分，那么两部分应该满足以下条件：
- 左半部分不能以 0 开头，除非左半部分只有 0；
- 右半部分不能以 0 结尾。
时间复杂度 $O(n^3)$，其中 $n$ 为字符串 $S$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | 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)
]
|
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
26
27 | 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 : f(s, 1, i)) {
for (String y : f(s, i, n - 1)) {
ans.add(String.format("(%s, %s)", x, y));
}
}
}
return ans;
}
private List<String> f(String s, int i, int j) {
List<String> res = new ArrayList<>();
for (int k = 1; k <= j - i; ++k) {
String l = s.substring(i, i + k);
String r = s.substring(i + k, j);
boolean ok = ("0".equals(l) || !l.startsWith("0")) && !r.endsWith("0");
if (ok) {
res.add(l + (k < j - i ? "." : "") + r);
}
}
return res;
}
}
|
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
26
27 | class Solution {
public:
vector<string> ambiguousCoordinates(string s) {
int n = s.size();
vector<string> ans;
auto f = [&](int i, int j) {
vector<string> res;
for (int k = 1; k <= j - i; ++k) {
string l = s.substr(i, k);
string r = s.substr(i + k, j - i - k);
bool ok = (l == "0" || l[0] != '0') && r.back() != '0';
if (ok) {
res.push_back(l + (k < j - i ? "." : "") + r);
}
}
return res;
};
for (int i = 2; i < n - 1; ++i) {
for (auto& x : f(1, i)) {
for (auto& y : f(i, n - 1)) {
ans.emplace_back("(" + x + ", " + y + ")");
}
}
}
return ans;
}
};
|
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
26
27
28 | func ambiguousCoordinates(s string) []string {
f := func(i, j int) []string {
res := []string{}
for k := 1; k <= j-i; k++ {
l, r := s[i:i+k], s[i+k:j]
ok := (l == "0" || l[0] != '0') && (r == "" || r[len(r)-1] != '0')
if ok {
t := ""
if k < j-i {
t = "."
}
res = append(res, l+t+r)
}
}
return res
}
n := len(s)
ans := []string{}
for i := 2; i < n-1; i++ {
for _, x := range f(1, i) {
for _, y := range f(i, n-1) {
ans = append(ans, "("+x+", "+y+")")
}
}
}
return ans
}
|
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
26 | function ambiguousCoordinates(s: string): string[] {
s = s.slice(1, s.length - 1);
const n = s.length;
const dfs = (s: string) => {
const res: string[] = [];
for (let i = 1; i < s.length; i++) {
const t = `${s.slice(0, i)}.${s.slice(i)}`;
if (`${Number(t)}` === t) {
res.push(t);
}
}
if (`${Number(s)}` === s) {
res.push(s);
}
return res;
};
const ans: string[] = [];
for (let i = 1; i < n; i++) {
for (const left of dfs(s.slice(0, i))) {
for (const right of dfs(s.slice(i))) {
ans.push(`(${left}, ${right})`);
}
}
}
return ans;
}
|