leetcode 93 复原ip地址

题目

leetcode 93 复原ip地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

分析

• ip 格式：4个字节，32bit位；如果以点十记法，3个.分割ip为四段，每段的值都不能大于255，且如果本段如果以0开始，那么只能是0，不能带有其他的数字
• 节点的解空间：
  • 1，2，3段: s字符串中最多3个字符，
  • 第4段：剩余的其他的字符
• 终止条件：路径长度大于4
• 解的判断：因为前面每段都是符合ip的格式，因此当终止时，路径就是解

code

class Solution {
    vector<string> result;
    vector<string> tmp;
    bool isIPSegment(const string& s){
        //以0开始的段，只能出现一个0
        if(s[0] == '0') return s.size() -1 == 0;
        //否则值应该小于256
        stringstream os(s);
        int i;
        os >> i;
        return i <= 255;
    }
    void backtrace(const string& s,int index,int level){
        if(level == 4){
            string t;
            for(const auto& it : tmp)
                t += it;
            result.push_back(std::move(t));
            return;
        }
        //最后一段，需要消费掉剩余的字符串
        if(level == 3){
            if(s.size() - 3 > index || s.size() <= index || !isIPSegment(s.substr(index))) return;
            tmp.push_back(s.substr(index));
            backtrace(s,index,level+1);
            tmp.pop_back();
            return;
        }
        //每段最多消费3个字符
        int size = min((int)s.size(),index + 3);
        // i 表示右边界，左边右开
        for(int i = index+1;i <= size; ++i){
            string sub = s.substr(index,i-index);
            if(!isIPSegment(sub)) return;
            tmp.push_back(s.substr(index,i-index)+".");
            backtrace(s,i,level+1);
            tmp.pop_back();
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        backtrace(s,0,0);
        return result;
    }
};