<p>We had some 2-dimensional coordinates, like <code>&quot;(1, 3)&quot;</code> or <code>&quot;(2, 0.5)&quot;</code>. Then, we removed all commas, decimal points, and spaces and ended up with the string s.</p>

<ul>
	<li>For example, <code>&quot;(1, 3)&quot;</code> becomes <code>s = &quot;(13)&quot;</code> and <code>&quot;(2, 0.5)&quot;</code> becomes <code>s = &quot;(205)&quot;</code>.</li>
</ul>

<p>Return <em>a list of strings representing all possibilities for what our original coordinates could have been</em>.</p>

<p>Our original representation never had extraneous zeroes, so we never started with numbers like <code>&quot;00&quot;</code>, <code>&quot;0.0&quot;</code>, <code>&quot;0.00&quot;</code>, <code>&quot;1.0&quot;</code>, <code>&quot;001&quot;</code>, <code>&quot;00.01&quot;</code>, or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like <code>&quot;.1&quot;</code>.</p>

<p>The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(123)&quot;
<strong>Output:</strong> [&quot;(1, 2.3)&quot;,&quot;(1, 23)&quot;,&quot;(1.2, 3)&quot;,&quot;(12, 3)&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(0123)&quot;
<strong>Output:</strong> [&quot;(0, 1.23)&quot;,&quot;(0, 12.3)&quot;,&quot;(0, 123)&quot;,&quot;(0.1, 2.3)&quot;,&quot;(0.1, 23)&quot;,&quot;(0.12, 3)&quot;]
<strong>Explanation:</strong> 0.0, 00, 0001 or 00.01 are not allowed.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(00011)&quot;
<strong>Output:</strong> [&quot;(0, 0.011)&quot;,&quot;(0.001, 1)&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>4 &lt;= s.length &lt;= 12</code></li>
	<li><code>s[0] == &#39;(&#39;</code> and <code>s[s.length - 1] == &#39;)&#39;</code>.</li>
	<li>The rest of <code>s</code> are digits.</li>
</ul>

class Solution {
    void filterNums(vector<string> &nums){
        auto swapRemove = [&nums](size_t i){
            swap(nums[i], nums[nums.size() - 1]);
            nums.pop_back();
        };

        for(int i = 0; i < nums.size(); ){
            const auto& num = nums[i];

            // Ends with 0
            if(num.size() > 1){
                const auto dotIt = find(num.begin(), num.end(), '.');
                
                // There is '.' but it ends with zero
                if(dotIt != num.end() && num.back() == '0'){
                    swapRemove(i);
                    continue;
                }
                // No '.' and starts with zero
                if(dotIt == num.end() && num.front() == '0'){
                    swapRemove(i);
                    continue;
                }

                // Starts with zero but is not 0.xxxx
                if(dotIt != num.begin() + 1 && num.front() == '0'){
                    swapRemove(i);
                    continue;
                }
            }

            ++i;
        }
    }

    // Returns all possible numbers with '.'
    vector<string> singleNum(const string& digits){
        vector<string> res;

        for(int i = 1; i < digits.size(); ++i){
            string first = digits.substr(0, i);
            string second = digits.substr(i, digits.size() - i);

            first.push_back('.');
            first += second;

            res.push_back(first);
        }

        if(!digits.empty()){
            res.push_back(digits);
        }

        return res;
    }

    void helper(vector<string> &res, const string& digits){
        for(size_t idx = 1; idx < digits.size(); ++idx){
            string first = digits.substr(0, idx);
            string second = digits.substr(idx, digits.size() - idx);

            //cout << "first: " << first << "; second: " << second << endl;

            auto firstNums = singleNum(first);
            auto secondNums = singleNum(second);

            filterNums(firstNums);
            filterNums(secondNums);

            // for(auto s : firstNums){
            //     cout << "first num: " << s << endl;
            // }

            // for(auto s : secondNums){
            //     cout << "second num: " << s << endl;
            // }

            for(const auto &num1 : firstNums){
                for(const auto &num2 : secondNums){
                    string tmp;
                    tmp.push_back('(');
                    tmp += num1;
                    tmp += ", ";
                    tmp += num2;
                    tmp.push_back(')');

                    res.push_back(move(tmp));
                }
            }
        }
    }

public:
    vector<string> ambiguousCoordinates(string s) {
        string digits = s.substr(1, s.size() - 2);

        vector<string> res;

        helper(res, digits);
        
        return res;
    }
};
15100