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

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

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example:

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

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的情况，没有考虑。

public class Solution {
    
   public ArrayList<String> restoreIpAddresses(String s) {
        return restoreIpAddresses(s, 4);
    }

    private ArrayList<String> restoreIpAddresses(String s, int nPos) {
        // nPos counting from 4 to 1,
        ArrayList<String> al = new ArrayList<String>();

        if (nPos == 1) {// treat the case when nPos == 1
            if (isValidIP(s))
                al.add(s);
            return al;
        }
        // nPos == 2, 3,4
        for (int len = 1; len <= Math.min(3, s.length()) ; len++) {// for string length of 1 ,2, 3
            String str = s.substring(0, len);
            if (!isValidIP(str))
                continue;
            ArrayList<String> restAl = restoreIpAddresses(s.substring(len), nPos - 1);
            // add str at the beginning of restAl
            for (String ss : restAl)
                al.add(str+"." + ss);
        }
        return al;
    }

    private boolean isValidIP(String s) {
        if (s.length() <= 0)
            return false;
        // cannot start from 0
        if(s.charAt(0) == '0' && s.length()>1)
            return false;
        int ip = 0;
        try {
            ip = Integer.parseInt(s);
        } catch (NumberFormatException NFE) {
            // System.out.println("number format exception");
        }

        if (ip == 0 && s.length() != 1)// if zero, and length() == 0
            return false;
        return ip >= 0 && ip <= 255;
    }
}

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

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