题目形容
这是 LeetCode 上的 816. 含糊坐标 ，难度为 中等。
Tag :「枚举」、「模仿」
咱们有一些二维坐标，如 "(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 中的左右括号去掉，从新定义 s 为原字符串 $s[1…(n – 2)]$，从新定义后的 s 长度为 n。
随后枚举逗号的地位 idx，枚举范畴为 $[0, n – 1)$，含意为在 $s[idx]$ 前面追加逗号。
此时右边局部字符串为 $s[0, idx]$，左边局部字符串为 $s[idx + 1, n – 1]$。
实现一个搜寻函数 List<String> search(int start, int end)，该函数返回应用字符串 $s[start…end]$ 结构的具体数值汇合。
假如右边字符串 $s[0, idx]$ 搜寻后果为 A，左边字符串 $s[idx + 1, n – 1]$ 搜寻后果为 B，依据「乘法原理」，可知所有理论计划为 (x, y) 其中 $x \in A$，$y \in B$。
思考如何实现 search 函数（假如入参函数 start 和 end 对应的子串为 sub）：枚举字符串追加小数点的地位 idx，枚举范畴为 $[start, end – 1)$，含意为在 $sub[idx]$ 前面追加小数点。小数点后面的局部不能蕴含前导零，小数点前面的局部不能蕴含后导零。留神记得把不增加小数点的非法计划也存入搜寻汇合。
Java 代码：
class Solution {
String s;
public List<String> ambiguousCoordinates(String _s) {s = _s.substring(1, _s.length() - 1);
int n = s.length();
List<String> ans = new ArrayList<>();
for (int i = 0; i < n - 1; i++) { // 枚举逗号：在 i 的前面追加逗号
List<String> a = search(0, i), b = search(i + 1, n - 1);
for (String x : a) {for (String y : b) {ans.add("(" + x + "," + y + ")");
}
}
}
return ans;
}
List<String> search(int start, int end) {List<String> ans = new ArrayList<>();
if (start == end || s.charAt(start) != '0') ans.add(s.substring(start, end + 1));
for (int i = start; i < end; i++) { // 枚举小数点：在 i 前面追加小数点
String a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1);
if (a.length() > 1 && a.charAt(0) == '0') continue;
if (b.charAt(b.length() - 1) == '0') continue;
ans.add(a + "." + b);
}
return ans;
}
}TypeScript 代码：
function ambiguousCoordinates(_s: string): string[] {function search(s: string, start: number, end: number): string[] {const ans = new Array<string>()
if (start == end || s[start] != '0') ans.push(s.substring(start, end + 1))
for (let i = start; i < end; i++) {const a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1)
if (a.length > 1 && a[0] == '0') continue
if (b[b.length - 1] == '0') continue
ans.push(a + '.' + b)
}
return ans
}
const s = _s.substring(1, _s.length - 1)
const n = s.length
const ans = new Array<string>()
for (let i = 0; i < n - 1; i++) {const a = search(s, 0, i), b = search(s, i + 1, n - 1)
for (const x of a) {for (const y of b) {ans.push('(' + x + ',' + y + ')')
}
}
}
return ans
}Python 代码：
class Solution:
def ambiguousCoordinates(self, _s: str) -> List[str]:
def search(s, start, end):
ans = []
if start == end or s[start] != '0':
ans.append(s[start:end+1])
for i in range(start, end):
a, b = s[start:i+1], s[i+1:end+1]
if len(a) > 1 and a[0] == '0':
continue
if b[-1] == '0':
continue
ans.append(f'{a}.{b}')
return ans
s = _s[1:len(_s)-1]
n = len(s)
ans = []
for i in range(n - 1):
a, b = search(s, 0, i), search(s, i + 1, n - 1)
for x in a:
for y in b:
ans.append(f'({x}, {y})')
return ans- 工夫复杂度：$O(n^3)$
- 空间复杂度：$O(n^3)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.816 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布