本文共 1716 字，大约阅读时间需要 5 分钟。

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)

dfs虽然早就熟悉，但驾驭起来还是非常欠火候，而且碰到问题除非非的用dfs才会考虑，看了博主的文章，觉得dfs很强大，理解了思路，就自己实现下，仔细体会下dfs，还真的有那么点味道，这个题目不难，ip在0.0.0.0 - 255.255.255.255都是合法的，这里的程序就不做解释了，建议若看的不是很明白就自己copy到本机环境中，去单步下，很有意思，理解也更深刻，这个题本身就是一个题，但是dfs的思想还是蛮有趣。

class Solution {public:    bool isValid(string sip){        if(sip.length() > 3 || sip.length() > 1 && sip[0] == '0') return false;        int sum = 0;        for(int i = 0; i < sip.length(); ++i){            sum *= 10;            sum += sip[i] - '0';        }        return (sum >= 0 && sum <= 255);    }    //ndot：ip地址四段三个“.",ndot表示已经处理的段数    //start：给定ip string 串的下标    void dfs(string s, int ndot, int start,string &cur_re, vector
   
     &re){        if(ndot > 3 || start >= s.length()) return;        if(ndot == 3 && isValid(s.substr(start))){            cur_re.append(s.substr(start));            re.push_back(cur_re);            return;        }        for(int i = start; i < s.length() && i - start < 3; ++i){            // i - start < 3 : 4位以上可定就不合法了，不用继续了。            string sub = s.substr(start, i - start + 1);            if(isValid(sub)){                int len = cur_re.length();                cur_re.append(sub + ".");                dfs(s, ndot + 1, i + 1, cur_re, re);                cur_re.resize(len);            }        }    }    vector
    
      restoreIpAddresses(string s) {        vector
     
       re;        string cur_re;        //再少不能少于4个吧，再多也别多于12位        if(s.length() < 4 || s.length() > 12) return re;        dfs(s, 0, 0, cur_re, re);        return re;    }};
     
    
   

转载地址：http://irlji.baihongyu.com/