LeetCode之“字符串”：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)

　　本题的解答参考自一博文：

　　首先我们要明确传统IP 地址的规律是分4个Part，每个Part是从0-255的数字0-255的数字，转换成字符，即每个Part 可能由一个字符组成，二个字符组成，或者是三个字符组成。那这又成为组合问题了，dfs便呼之欲出。所以我们写一个For循环每一层从1个字符开始取一直到3个字符，再加一个isValid的函数来验证取的字符是否是合法数字，如果是合法的数字，我们再进行下一层递归，否则跳过。

　　几点注意的地方：

　　1. 在验证字符串是否是数字的时候，要注意0的情况，001，010，03都是非法的。所以，如果第一位取出来是0，那么我们就判断字符串是否是"0"，不是的情况都是非法的

　　2. 取字符串的时候，注意位数不够的问题，不仅<4, 而且<s.size()

　　3. 注意substr的范围

　　4. 字符串转换成数字 atoi(s.c_str()); 

　　5. 别忘了IP 地址里面的 "."

　　6. 到第4个Part的时候我们就可以整体验证剩下的所有字符串（因为第4个Part最后一定要取到结尾才是正确的字符串）

class Solution {
public:
    bool isValid(string s)
    {
        int sz = s.size();
        if(sz == 0 || sz > 3)
            return false;
            
        if(s[0] == '0')
            return s == "0";
            
        int num = atoi(s.c_str());
        return num <= 255 && num > 0;
    }
    
    void dfs(string s, string tmp, vector<string>& res, int count)
    {
        if(count == 3 && isValid(s))
        {
            res.push_back(tmp + s);
            return;
        }
        for(int i = 1; i < 4 && i < s.size(); i++)
        {
            string str = s.substr(0, i);
            if(isValid(str))
                dfs(s.substr(i), tmp + str + '.', res, count + 1);
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        int sz = s.size();
        if(sz < 4 || sz > 12)
            return res;
        
        dfs(s, "", res, 0);
        return res;
    }
};