<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:
    vector<pair<string, string>> divide(string s)
    {
        vector<pair<string,string>> dividedString;
        for(int i = 1 ; i+2 < s.length() ; i++)
        {
            string first = string(s.begin()+1, s.begin()+i+1);
            string second = string(s.begin()+i+1, s.end()-1);
            dividedString.push_back({first, second});
        }
        return  dividedString;
    }

    vector<string> pointify(string dig)
    {
        vector<string> pointifiedString;
        pointifiedString.push_back(dig);
        for(int i = 0 ; i < dig.size() ; i++)
        {
            string first = string(dig.begin(), dig.begin()+i+1);
            string second = string(dig.begin()+i+1, dig.end());
            if(second.size() != 0)
            {
                pointifiedString.push_back(first+"."+second);
            }
        }
        return pointifiedString;
    }
 bool isValid(string s) {
    if (s.find('.') != string::npos) {
        size_t dotPosition = s.find('.');
        string integerPart = s.substr(0, dotPosition);
        string decimalPart = s.substr(dotPosition + 1);

        if (integerPart != "0" && integerPart[0] == '0') {
            return false;
        } else {
            return !decimalPart.ends_with("0");
        }
    } else {
        if (s == "0") {
            return true;
        } else {
            return !s.starts_with("0");
        }
    }
}

    vector<string> ambiguousCoordinates(string s) {
        //Divide
        //Pointify
        //Prune
        vector<pair<string,string>> dividedString = divide(s);
        vector<string> ans;
        for(auto pairOfString : dividedString)
        {
            string firstDig = pairOfString.first;
            string secondDig = pairOfString.second;
            vector<string> pointifiedString1 = pointify(firstDig);
            vector<string> pointifiedString2 = pointify(secondDig);
            for(auto firstInt : pointifiedString1)
            {
                for(auto secondInt : pointifiedString2)
                {
                    if(isValid(firstInt) && isValid(secondInt))
                    {
                        string currentAnswer = "("+firstInt+", "+secondInt+")";
                        ans.push_back(currentAnswer);
                    }
                }
            }
        }
        return ans;
        
    }
};
16800