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 的情况,是不允许的
No comments:
Post a Comment