Easy division
Intuition\n Describe your first thoughts on how to solve this problem. \nsuppose s=pre+suf, the corresponding coordinates include the join of all possible divis
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsuppose s=pre+suf, the corresponding coordinates include the join of all possible divisions of pre/suf. Note that, for any pre/suf, it is not valid for division if the length of it is larger than 1 and both the front and end of it are \'0\'s.\n\n\n# Complexity\n- Time complexity: $$O(n^3)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^3)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    unordered_map<string,vector<string>> mp;\n    vector<string> helper(string&s){\n        if(mp.count(s)) return mp[s];\n        if(s.size()>1 and s[0]==\'0\' and s.back()==\'0\') return {};\n        if(s.back()==\'0\'){\n            mp[s]={s};\n            return mp[s];\n        }\n        if(s[0]==\'0\'){\n            string tmp=s.substr(0,1)+\'.\'+s.substr(1);\n            mp[s]={tmp};\n            return mp[s];\n        }\n        for(int i=1;i<s.size();i++){\n            string tmp=s.substr(0,i)+\'.\'+s.substr(i);\n            mp[s].emplace_back(tmp);\n        }\n        mp[s].emplace_back(s);\n        return mp[s];\n    }\npublic:\n    vector<string> ambiguousCoordinates(string s) {\n        vector<string> result;\n        for(int i=1;i+2<s.size();i++){\n            string pre=s.substr(1,i),suf=s.substr(i+1,s.size()-i-2);\n            auto ss1=helper(pre);\n            auto ss2=helper(suf);\n            if(ss1.empty() or ss2.empty())  continue;\n            for(auto&x:ss1) for(auto&y:ss2){\n                    string tmp="("+x+", "+y+")";\n                    result.emplace_back(tmp);\n                }\n        }\n        return result;\n    }\n};\n```
['C++']