816.模糊坐标

链接：816.模糊坐标
难度：Medium
标签：字符串、回溯、枚举
简介：返回所有可能的原始字符串到一个列表中。

题解 1 - cpp

• 编辑时间：2022-11-07
• 执行用时：8ms
• 内存消耗：10MB
• 编程语言：cpp
• 解法介绍：组合。

class Solution {
public:
    vector<string> ambiguousCoordinates(string s) {
        vector<string> ans;
        int n = s.size();
        for (int i = 2; i < n - 1; i++) {
            for (auto &l : comp(s.substr(1, i - 1))) {
                for (auto &r: comp(s.substr(i, s.size() - 1 - i))) {
                    ans.push_back("(" + l + ", " + r + ")");
                }
            }
        }
        return ans;
    }
    vector<string> comp(string str) {
        vector<string> list;
        int f = check1(str);
        if (f) list.push_back(str);
        if (str.size() > 1) {
            for (int i = 1; i < str.size(); i++) {
                string next = str.substr(0, i) + "." + str.substr(i);
                int f = check2(next, i);
                if (f) list.push_back(next);
            }
        }
        return list;
    }
    bool check1(string &str) {
        if (str[0] == '0' && str.size() != 1) return false;
        return true;
    }
    bool check2(string &str, int idx) {
        // 开头不能是0，除非只有0
        if (str[0] == '0' && idx != 1) return false;
        // 结尾不能是0
        if (str.back() == '0') return false;
        // 小数不能全0
        int f = true;
        for (int i = idx + 1; i < str.size(); i++) {
            if (str[i] != '0') {
                f = false;
                break;
            }
        }
        if (f) return false;
        return true;
    }
};