[数据结构与算法]【力扣】[回溯] LeetCode93.复原 IP 地址

1、题目

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

链接：https://leetcode-cn.com/problems/restore-ip-addresses

?

2、思路分析

1）回溯

class Solution {
public:
    static constexpr int count = 4;
    vector<string> res;
    vector<int> nums;

    void dfs(const string& s, int numsId, int start)
    {
        if(numsId == count){ // 当达到四段的时候，并且start走到了最后，那么就是一种结果
            if(start == s.size()){
                string t = "";
                for(int i = 0; i < count; ++i){
                    t += to_string(nums[i]);
                    if(i != count-1){
                        t += "."; // 最后一次不加 .
                    }  
                }
                res.push_back(t);
            }
            return;
        }
        // 如果此时没有4段ip，则直接返回
        if(start == s.size()){
            return;
        }
        // 处理前导0
        if(s[start] == '0'){
            nums[numsId] = 0;
            dfs(s, numsId + 1, start + 1);
        }
        int addr = 0;
        for(int i = start; i < s.size(); ++i){
            addr = addr * 10 + (s[i] - '0'); // 这里将每一种可能的结果都给出
            if(addr > 0 && addr <= 0xff){
                nums[numsId] = addr;
                dfs(s, numsId + 1, i + 1); // 这里一定是i+1，因为每次都要选之后的字符
            }
            else {
                break;
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        nums.resize(count);  // 开辟四段空间
        dfs(s, 0, 0);
        return res;
    }
};