题目链接：93. 复原IP地址

题解：

带有剪枝的搜索，挺有意思！

题目简述：

给定一串数字，需要将其可以转化为的IP地址返回！

题解：

暴力搜索DFS：void dfs(string s, int u, int k, string path)

  • u：当前搜索到的位置
  • k：当前搜索的点的个数
  • path：当前状态下的IP地址

思路：

  • 对于前导0的处理，即012，IP地址没有前导0的，这个已经见过很多次了，直接i > u && s[u] == '0'即可判断！
  • 然后搜索下一位时保证下一位在0 ~ 255范围即为合法数字，否则直接return
  • 下一个数的搜索要从上一个数的后一位开始，即i = u开始

终止条件：

  • u == s.size()：即搜到了字符串末尾
  • 剪枝优化：u < s.size() && k == 4：即没有搜到最后，已经够了四个点

答案： u == s.size() && k == 4：即恰好组成一组IP地址，此时将该IP地址path最后的小数点去掉，即为答案

时间复杂度：一共n位，n - 1个空隙可插入点，即从n - 1个空隙三个点，即时间复杂度为：Cn-13

AC代码：

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
    void dfs(string s, int u, int k, string path){
        if(u == s.size()){
            if(k == 4){
                path.pop_back();
                res.push_back(path);
            }
            return;
        }
        if(k == 4) return;
        for(int i = u, t = 0; i < s.size(); i++){
            if(i > u && s[u] == '0') return;
            t = t * 10 + s[i] - '0';
            if(t <= 255) dfs(s, i + 1, k + 1, path + to_string(t) + '.');
            else return;
        }
    }
};