93. Restore IP Addresses -------M ！

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

 

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

 

Constraints:

• 1 <= s.length <= 20
• s consists of digits only.

A:

每次计算下一步的。 然后把所有的再合起来，加到结果上
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        return helper(s,4);
    }
private:
    vector<string> helper(string s, int k){        
        vector<string> res;
        if(s.length() > k*3 || s.length() < k){ // if not valid input
            return res;
        }
        if(k == 1){
            if( stoi(s) <= 255 && ( s=="0" || s[0] !='0' )){
                res.push_back(s);
            }
        }else{
            for(int len = 1; len<= min(3,(int)(s.length()));len++){
                string val = s.substr(0,len);
                if(len != 1 && val[0]=='0' ){
                    break;
                }
                if(stoi(val) <= 255){
                    auto sub = helper(s.substr(len), k -1);
                    for(auto line : sub)
                        res.push_back(val+"."+line);
                }
            }
        }
       return res;
    }
};

Mistakes:

3:  valid ID 不能以0 开头，除非 他只有一个零。

Learned:
1: string to int, 可以用Integer.parseInt(String s)来转换，记住要捕获一个NumberFormatException

--------------------第二遍--------用recursive 来代替。------------------------

1： 不能仅仅检查是否是0，和长度为1。 因为有可能是00的情况。 所以要检查int的值。
2：  len <= Math.min(3, s.length()) 的原因是，  有可能，len取不够3个字符的。 例如对于输入2222。
3:   010的情况，没有考虑。

直接dfs， 如果合适，就把结果加入到最终结果。 因此需要有preStr 这个来记录之前的路径

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string pre;
        dfs(s, res, pre, 0, 4);
        return res;
    }
private:
    void dfs(string& s, vector<string>& res, string pre, int start, int oneTo4) {
        int n = s.length();
        if (start >= n) {
            return;
        }
        if (oneTo4 == 1) {
            string tmp = s.substr(start);
            if(isValid(tmp))
                res.push_back(pre + tmp);
        } else {
            for(int len = 1; len<=3; len++){
                if(start + len < n){
                    string tmp = s.substr(start, len);
                    if(isValid(tmp)){
                        dfs(s, res, pre+tmp+".", start + len, oneTo4-1);
                    }
                }
            }
        }
    }
private:
    bool isValid(string candidate) {
        if (candidate.length() > 1 && candidate[0] == '0') {
            return false;
        }
        if (candidate.length() > 3) // in case too long
            return false;
        return stoi(candidate) < 256;
    }
};

------------------------3 rd Pass -------和第二遍一样-------------------------------
 和第二遍的区别是，没有用Iteger.parseInteger, 而是自己写循环计算的。  

Error:
   没考虑 001 的情况，是不允许的