TNotes.leetcode

Appearance

⏰0816. 模糊坐标【中等】

0816. 模糊坐标【中等】 ​

1. 📝 题目描述 ​

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例 1：

txt
输入: "(123)"
输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

示例 2：

txt
输入: "(00011)"
输出:  ["(0.001, 1)", "(0, 0.011)"]
解释:
0.0, 00, 0001 或 00.01 是不被允许的。

示例 3：

txt
输入: "(0123)"
输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

示例 4:

txt
输入: "(100)"
输出: [(10, 0)]
解释:
1.0 是不被允许的。

提示：

  • 4 <= S.length <= 12.
  • S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。

2. 🎯 s.1 - 枚举 ​

c
int getValid(char* s, int start, int len, char** results) {
    int cnt = 0;
    char sub[len + 1];
    strncpy(sub, s + start, len);
    sub[len] = '\0';
    if (len == 1 || sub[0] != '0') {
        results[cnt] = (char*)malloc(len + 1);
        strcpy(results[cnt++], sub);
    }
    for (int i = 1; i < len; i++) {
        if (i > 1 && sub[0] == '0') continue;
        if (sub[len - 1] == '0') continue;
        results[cnt] = (char*)malloc(len + 2);
        strncpy(results[cnt], sub, i);
        results[cnt][i] = '.';
        strncpy(results[cnt] + i + 1, sub + i, len - i);
        results[cnt][len + 1] = '\0';
        cnt++;
    }
    return cnt;
}

char** ambiguousCoordinates(char* s, int* returnSize) {
    int n = strlen(s) - 2;
    char* str = s + 1;
    char** res = (char**)malloc(sizeof(char*) * 1000);
    *returnSize = 0;
    char* left[20], *right[20];
    for (int i = 1; i < n; i++) {
        int lCnt = getValid(str, 0, i, left);
        int rCnt = getValid(str, i, n - i, right);
        for (int a = 0; a < lCnt; a++)
            for (int b = 0; b < rCnt; b++) {
                res[*returnSize] = (char*)malloc(strlen(left[a]) + strlen(right[b]) + 5);
                sprintf(res[*returnSize], "(%s, %s)", left[a], right[b]);
                (*returnSize)++;
            }
        for (int a = 0; a < lCnt; a++) free(left[a]);
        for (int b = 0; b < rCnt; b++) free(right[b]);
    }
    return res;
}
js
/**
 * @param {string} s
 * @return {string[]}
 */
var ambiguousCoordinates = function (s) {
  const str = s.slice(1, -1)
  const res = []
  for (let i = 1; i < str.length; i++) {
    const left = valid(str.slice(0, i))
    const right = valid(str.slice(i))
    for (const l of left) for (const r of right) res.push(`(${l}, ${r})`)
  }
  return res
}

function valid(s) {
  const res = []
  if (s === '0' || s[0] !== '0') res.push(s)
  for (let i = 1; i < s.length; i++) {
    const left = s.slice(0, i),
      right = s.slice(i)
    if ((left.length > 1 && left[0] === '0') || right[right.length - 1] === '0')
      continue
    res.push(left + '.' + right)
  }
  return res
}
py
class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        def valid(t: str) -> list:
            res = []
            if t == '0' or t[0] != '0':
                res.append(t)
            for i in range(1, len(t)):
                left, right = t[:i], t[i:]
                if (len(left) > 1 and left[0] == '0') or right[-1] == '0':
                    continue
                res.append(left + '.' + right)
            return res
        s = s[1:-1]
        ans = []
        for i in range(1, len(s)):
            for l in valid(s[:i]):
                for r in valid(s[i:]):
                    ans.append(f'({l}, {r})')
        return ans
  • 时间复杂度：O(n3)，其中 n 是字符串长度
  • 空间复杂度：O(n3)

算法思路：

  • 枚举逗号分割位置，对左右两部分分别枚举所有合法的小数表示
  • 合法性检查：无前导零（除非就是 "0"）、无后缀零（小数部分）