Medium
题目描述
我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"。然后，我们移除所有逗号、小数点和空格，得到字符串 s。
- 例如，
"(1, 3)"变成s = "(13)"，"(2, 0.5)"变成s = "(205)"。
返回一个字符串列表，表示我们原始坐标可能的所有情况。
我们的原始表示从来没有多余的零，所以我们从来不会以 "00"、"0.0"、"0.00"、"1.0"、"001"、"00.01" 或任何其他可以用更少数字表示的数字开始。同样，数字中的小数点前至少要有一位数字，所以我们从来不会以 ".1" 这样的数字开始。
最终答案列表可以按任何顺序返回。最终答案中的所有坐标在它们之间有恰好一个空格（出现在逗号之后）。
示例 1：
输入：s = "(123)"
输出：["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]
示例 2：
输入：s = "(0123)"
输出：["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]
解释：0.0, 00, 0001 或 00.01 是不允许的。
示例 3：
输入：s = "(00011)"
输出：["(0, 0.011)","(0.001, 1)"]
约束条件：
4 <= s.length <= 12s[0] == '('且s[s.length - 1] == ')'s的其余部分都是数字。
解题思路
这道题的核心思路是枚举所有可能的坐标分割方式，然后对每一部分生成所有有效的数字表示。
解题步骤：
分割字符串：去掉首尾的括号后，枚举所有可能的分割点，将字符串分成两部分作为 x 坐标和 y 坐标。
生成有效数字：对每一部分，生成所有可能的有效数字表示（整数或小数）。需要遵循以下规则：
- 整数不能有前导零（除非是单独的"0"）
- 小数的整数部分不能有前导零（除非是单独的"0"）
- 小数的小数部分不能有后缀零
验证函数：实现一个函数来判断数字字符串是否有效：
- 对于整数：不能有前导零（“0"除外）
- 对于小数：整数部分和小数部分都要符合规则
组合结果：将所有有效的 x 坐标和 y 坐标组合，形成最终结果。
具体实现策略：
- 先写一个辅助函数生成单个数字串的所有有效表示
- 然后枚举所有分割点，对左右两部分分别调用辅助函数
- 最后将所有组合拼接成坐标格式
代码实现
class Solution {
public:
vector<string> ambiguousCoordinates(string s) {
vector<string> result;
string nums = s.substr(1, s.length() - 2); // 去掉括号
for (int i = 1; i < nums.length(); i++) {
string left = nums.substr(0, i);
string right = nums.substr(i);
vector<string> leftCandidates = generateNumbers(left);
vector<string> rightCandidates = generateNumbers(right);
for (const string& l : leftCandidates) {
for (const string& r : rightCandidates) {
result.push_back("(" + l + ", " + r + ")");
}
}
}
return result;
}
private:
vector<string> generateNumbers(const string& s) {
vector<string> result;
// 作为整数
if (isValidInteger(s)) {
result.push_back(s);
}
// 作为小数
for (int i = 1; i < s.length(); i++) {
string intPart = s.substr(0, i);
string fracPart = s.substr(i);
if (isValidInteger(intPart) && isValidFraction(fracPart)) {
result.push_back(intPart + "." + fracPart);
}
}
return result;
}
bool isValidInteger(const string& s) {
return s == "0" || (s[0] != '0' && !s.empty());
}
bool isValidFraction(const string& s) {
return !s.empty() && s.back() != '0';
}
};
class Solution:
def ambiguousCoordinates(self, s: str) -> List[str]:
result = []
nums = s[1:-1] # 去掉括号
for i in range(1, len(nums)):
left = nums[:i]
right = nums[i:]
left_candidates = self.generate_numbers(left)
right_candidates = self.generate_numbers(right)
for l in left_candidates:
for r in right_candidates:
result.append(f"({l}, {r})")
return result
def generate_numbers(self, s):
result = []
# 作为整数
if self.is_valid_integer(s):
result.append(s)
# 作为小数
for i in range(1, len(s)):
int_part = s[:i]
frac_part = s[i:]
if self.is_valid_integer(int_part) and self.is_valid_fraction(frac_part):
result.append(int_part + "." + frac_part)
return result
def is_valid_integer(self, s):
return s == "0" or (s and s[0] != "0")
def is_valid_fraction(self, s):
return s and s[-1] != "0"
public class Solution {
public IList<string> AmbiguousCoordinates(string s) {
var result = new List<string>();
string nums = s.Substring(1, s.Length - 2); // 去掉括号
for (int i = 1; i < nums.Length; i++) {
string left = nums.Substring(0, i);
string right = nums.Substring(i);
var leftCandidates = GenerateNumbers(left);
var rightCandidates = GenerateNumbers(right);
foreach (string l in leftCandidates) {
foreach (string r in rightCandidates) {
result.Add($"({l}, {r})");
}
}
}
return result;
}
private List<string> GenerateNumbers(string s) {
var result = new List<string>();
// 作为整数
if (IsValidInteger(s)) {
result.Add(s);
}
// 作为小数
for (int i = 1; i < s.Length; i++) {
string intPart = s.Substring(0, i);
string fracPart = s.Substring(i);
if (IsValidInteger(intPart) && IsValidFraction(fracPart)) {
result.Add(intPart + "." + fracPart);
}
}
return result;
}
private bool IsValidInteger(string s) {
return s == "0" || (s.Length > 0 && s[0] != '0');
}
private bool IsValidFraction(string s) {
return s.Length > 0 && s[s.Length - 1] != '0';
}
}
var ambiguousCoordinates = function(s) {
const str = s.slice(1, -1);
const result = [];
function isValid(num) {
if (num.length === 1) return true;
if (num.includes('.')) {
const parts = num.split('.');
if (parts[0].length > 1 && parts[0][0] === '0') return false;
if (parts[1][parts[1].length - 1] === '0') return false;
return true;
}
return num[0] !== '0';
}
function getValidNumbers(s) {
const numbers = [];
if (isValid(s)) numbers.push(s);
for (let i = 1; i < s.length; i++) {
const num = s.slice(0, i) + '.' + s.slice(i);
if (isValid(num)) numbers.push(num);
}
return numbers;
}
for (let i = 1; i < str.length; i++) {
const left = str.slice(0, i);
const right = str.slice(i);
const leftNums = getValidNumbers(left);
const rightNums = getValidNumbers(right);
for (const l of leftNums) {
for (const r of rightNums) {
result.push(`(${l}, ${r})`);
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 大小 | 说明 |
|---|---|---|
| 时间复杂度 | O(n³) | 其中 n 是字符串长度。需要枚举 O(n) 个分割点，每个分割点生成 O(n) 个数字候选，组合时需要 O(n²) |
| 空间复杂度 | O(n³) | 存储所有可能的数字组合和最终结果 |