模拟

一次遍历 sss ，尝试对遍历到的位置进行分割。对分割点左右字符串 ltltlt , rtrtrt 分别构造子串。
构造子串的规则:

1. 整数不以 000 开头，(特例)单独的 000 可以作为整数。
2. 小数不以 000 结尾。
3. 小数的整数位是 000 ，则整数位不能组成新数。(规则 111 .)

代码展示

class Solution {
public:vector get_pos(string s){//生成子串符合条件的所有整数,和小数形式vector pos;if(s[0]!='0' || s =="0") pos.push_back(s);//整数子串//不以0开头,或者单走一个0。for(int p= 1;p//小数子串if((p!=1&&s[0]=='0')||s.back()=='0') continue;//不以0结尾//小数的整数部分以0开头,只有以0开头的组合。pos.push_back(s.substr(0,p)+'.'+s.substr(p,s.size()-1));//0到p-1做整数，p到s.size()-1位做小数。}return pos;}vector ambiguousCoordinates(string s) {int n = s.length() - 2;//倒数第2个是数字。最后一个是')'vector ans;s = s.substr(1,n);//只处理数字for(int i =1;i//第1个到n-2是数字vector lt=get_pos(s.substr(0,i));if(lt.empty()) continue;//没有对应子串vector rt=get_pos(s.substr(i));if(rt.empty()) continue;for(auto l:lt)//如果lt,rt有空，不会执行这一步for(auto r:rt)//组合//左半//右半ans.push_back('('+l+", "+r+')');}return ans;}
};

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度:O(n3)O(n^3)O(n3)， nnn 是 sss 的长度。生成 rtrtrt 和 ltltlt 的时间复杂度是 O(n2)O(n^2)O(n2) ，将 rtrtrt 和 ltltlt 内的数，保存到 ansansans 的时间复杂度是 O(n3)O(n^3)O(n3) 。
2. 空间复杂度:O(n3)O(n^3)O(n3)。用于存储答案的空间开销,如rt,lt,posrt,lt,posrt,lt,pos，最坏空间复杂度 O(n3)O(n^3)O(n3)。