<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 {
public:
    
    bool valid(string t) { // is this coord valid? 
        int i=1,n=t.size();
        if(n>=2 and t[0]=='0' and t[1]!='.') // 01, 03... --> not valid
            return false;
        
        while(i<n and t[i]!='.') // get position of the point
              i++;
        if(i!=n and t[n-1]=='0') // 234.0, 931.424320 --> not valid
            return false;
        i++;
        while(i<n and t[i]=='0') // if after the point are all zeros, not valid
            i++;
        if(i==n) return false;
        
        return true; // if here, coord is valid
   }
    
    void get_coord(string s1, string s2, vector<string>& res) {
        int n1=s1.size(), n2=s2.size();
        for(int i=0;i<n1;i++){ 
            // get every possible partition, as before, but with point at the middle
            // es. s1 = 1234 -> (.1234), (1.234), (12.234), (123.4)
            string s11 = s1.substr(0,i);
            string s12 = s1.substr(i);
            string t1 = s11 + "." + s12;
            if(t1[0] == '.') // remove initial point if present
                t1=t1.substr(1);
            if(valid(t1)){ // if it is valid, look at the second string
                for(int i=0;i<n2;i++){
                    string s21 = s2.substr(0,i);
                    string s22 = s2.substr(i);  
                    string t2 = s21 + "." + s22;
                    if(t2[0] == '.') // remove initial point if present
                        t2=t2.substr(1);
                    if(valid(t2)){ // if the second is valid too, add to res
                        res.push_back("("+t1+", "+t2+")");
                    }
                }
            }
        }
    }   
    
    vector<string> ambiguousCoordinates(string s) {
        s = s.substr(1,s.size()-2); // string without ( )
        vector<string> res;
        int n=s.size();
        for(int i=0;i<n;i++) {
            // get every double partition of string
            // es. s = 1234 -> (, 1234), (1, 234), (12, 234), (123, 4)
            get_coord(s.substr(0,i), s.substr(i), res); 
        }
        return res;
    }
};
12800