力扣(LeetCode)816. 模糊坐标(C++)

模拟

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

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

代码展示

class Solution {
public:
    vector<string> get_pos(string s){//生成子串符合条件的所有整数,和小数形式
        vector<string> pos;
        if(s[0]!='0' || s =="0") pos.push_back(s);//整数子串//不以0开头,或者单走一个0。
        for(int p= 1;p<s.size();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<string> ambiguousCoordinates(string s) {
        int n = s.length() - 2;//倒数第2个是数字。最后一个是')'
        vector<string> ans;
        s = s.substr(1,n);//只处理数字
        for(int i =1;i<n;i++){//第1个到n-2是数字
            vector<string> lt=get_pos(s.substr(0,i));
            if(lt.empty()) continue;//没有对应子串
            vector<string> 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

博主致语

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

AC

复杂度分析

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