816

class Solution {
public:
    vector<string> ambiguousCoordinates(string s) {
        int n = s.size();
        vector<string> ans;

        for(int i=1; i<n-2; i++){
            vector<string> left = getAll(s.substr(1, i));
            vector<string> right = getAll(s.substr(i+1, n-2-i));
            for(auto first: left)
                for(auto second: right)
                    ans.push_back("("+first+", "+second+")");
        }
        return ans;
    }

    vector<string> getAll(string s){
        int n = s.size();
        if(n == 0) return {};
        if(n == 1 && s[n-1] == '0') return {s};
        if(n > 1 && s[0] == '0' && s[n-1] != '0') return {s.substr(0,1)+"."+s.substr(1, n-1)};
        if(n > 1 && s[0] != '0' && s[n-1] == '0') return {s};
        if(n == 2 && s == "00") return {};
        if(n > 2 && s[0] == '0' && s[n-1] == '0'){
            return {};
        }

        vector<string> comb;
        comb.push_back(s);
        for(int i=1; i<n; i++){
            comb.push_back(s.substr(0,i)+"."+s.substr(i));
        }
        return comb;
        return {};
    }

};