Ambiguous Coordinates

medium backtracking strings enumeration

Problem

We had a coordinate like "(1, 3)" but all punctuation, spaces and decimal points were removed leaving a digit string s with surrounding parentheses. Return all valid coordinates that could produce s; each component must not have leading zeros (except "0" or "0.xxx") and not trailing zeros after a decimal.

Inputs = "(123)"

Output["(1, 23)","(12, 3)","(1.2, 3)","(1, 2.3)"]

Place comma in each split and enumerate decimal points on each side.

def ambiguousCoordinates(s):
    def options(d):
        if not d: return []
        if d == '0': return ['0']
        if d[-1] == '0': return [d] if d[0] != '0' else []
        if d[0] == '0': return ['0.' + d[1:]]
        return [d] + [d[:i] + '.' + d[i:] for i in range(1, len(d))]
    s = s[1:-1]
    out = []
    for i in range(1, len(s)):
        for a in options(s[:i]):
            for b in options(s[i:]):
                out.append(f"({a}, {b})")
    return out

var ambiguousCoordinates = function(s) {
    const options = (d) => {
        if (!d) return [];
        if (d === '0') return ['0'];
        if (d.endsWith('0')) return d[0] !== '0' ? [d] : [];
        if (d.startsWith('0')) return ['0.' + d.slice(1)];
        const res = [d];
        for (let i = 1; i < d.length; i++) res.push(d.slice(0, i) + '.' + d.slice(i));
        return res;
    };
    s = s.slice(1, -1);
    const out = [];
    for (let i = 1; i < s.length; i++) {
        for (const a of options(s.slice(0, i)))
            for (const b of options(s.slice(i)))
                out.push(`(${a}, ${b})`);
    }
    return out;
};

class Solution {
    public java.util.List<String> ambiguousCoordinates(String s) {
        s = s.substring(1, s.length() - 1);
        java.util.List<String> out = new java.util.ArrayList<>();
        for (int i = 1; i < s.length(); i++) {
            for (String a : options(s.substring(0, i)))
                for (String b : options(s.substring(i)))
                    out.add("(" + a + ", " + b + ")");
        }
        return out;
    }
    private java.util.List<String> options(String d) {
        java.util.List<String> r = new java.util.ArrayList<>();
        if (d.isEmpty()) return r;
        if (d.equals("0")) { r.add("0"); return r; }
        if (d.endsWith("0")) { if (d.charAt(0) != '0') r.add(d); return r; }
        if (d.startsWith("0")) { r.add("0." + d.substring(1)); return r; }
        r.add(d);
        for (int i = 1; i < d.length(); i++) r.add(d.substring(0, i) + "." + d.substring(i));
        return r;
    }
}

class Solution {
    vector<string> options(const string& d) {
        vector<string> r;
        if (d.empty()) return r;
        if (d == "0") { r.push_back("0"); return r; }
        if (d.back() == '0') { if (d.front() != '0') r.push_back(d); return r; }
        if (d.front() == '0') { r.push_back("0." + d.substr(1)); return r; }
        r.push_back(d);
        for (size_t i = 1; i < d.size(); i++) r.push_back(d.substr(0, i) + "." + d.substr(i));
        return r;
    }
public:
    vector<string> ambiguousCoordinates(string s) {
        s = s.substr(1, s.size() - 2);
        vector<string> out;
        for (size_t i = 1; i < s.size(); i++) {
            for (auto& a : options(s.substr(0, i)))
                for (auto& b : options(s.substr(i)))
                    out.push_back("(" + a + ", " + b + ")");
        }
        return out;
    }
};

Explanation

The coordinate had a comma splitting it into two parts, and each part may have had a decimal point. So we enumerate every split into a left and right block, then list all legal number forms for each block and pair them up.

The helper options(d) returns all valid numbers a digit block can become. The rules ban bad zeros: a block like "00" is invalid, a leading zero forces the form 0.xxx, and a trailing zero forbids a decimal point (no "1.20").

For a clean block such as "123", the options are the whole integer plus every decimal placement: 123, 1.23, 12.3.

The main loops strip the parentheses, choose a split index i, then take the cross product of options(left) and options(right), formatting each pair as (a, b).

Example: "(123)". Splitting after 1 gives left "1" → [1] and right "23" → [23, 2.3]; splitting after 12 gives [12, 1.2] and [3]. Collected, the result is ["(1, 23)","(1, 2.3)","(12, 3)","(1.2, 3)"].

Time: O(n^3) Space: O(n^2)