093 - Restore IP Addresses

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Hide Tags

Backtracking String

回溯，检查结果范围即可。
需要注意的是 ”00” ，“010” 不能算有效的分割，也就是说，处理了第一个 0 之后，应该break出来。
这里用的是检查从子串 sub 转出来的 val，再转回字符串是不是跟之前的 sub 一样，这样也可以避免上述问题。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> rst;
        string buf;
        int len=s.length();
        if(3<len && 13>len)
            build(s, s.length(), 0, 0, buf, rst);
        return rst;
    }
   
    void build(string s, int len, int pos, int section, string& buf, vector<string>& rst)
    {
        string sub="";
        int val=0;
       
        if(3==section)
        {
            sub = s.substr(pos, len-pos), val = atoi(sub.data());
            if((sub==to_string(val)) && 255>=val && 0<=val)
                   rst.push_back(buf+sub);
            return;
        }

        int endpos = len-(3-section);
        for(int nextpos=pos;nextpos<endpos; ++nextpos)
        {
            sub = s.substr(pos, nextpos-pos+1), val = atoi(sub.data());
            if((sub==to_string(val)) && 255>=val && 0<=val)
            {
                int ll=sub.length()+1;
                buf += sub + '.';
                build(s, len, nextpos+1, section+1, buf, rst);
                while(ll--)
                    buf.pop_back();
            }
        }
    }
};
4 ms.