426.Restore IP Addresses-恢复IP地址（中等题）

恢复IP地址

题目

给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。

样例

给出字符串 “25525511135”，所有可能的IP地址为： [ “255.255.11.135”, “255.255.111.35” ] （顺序无关紧要）

题解

还是回溯法解题，需注意合法的IP地址需满足： 1.每一个8位段的十进制取值范围为[0,255]。 2.每一个8位段的长度都不能大于3。 3.每一个8位段都不能出现如01、023这种情况。

public class Solution { /** * @param s the IP string * @return All possible valid IP addresses */ public ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> res = new ArrayList<String>(); find(res,s,new StringBuilder(),0,0); return res; } private void find(ArrayList<String> res,String s,StringBuilder sb,int count,int index) { if (count == 3) { String str = s.substring(index,s.length()); if (str.length() > 0) { if ((str.length() > 1 && str.charAt(0) == '0') || (Integer.valueOf(str) > 255 || str.length() > 3)) { return; } sb.append(str); res.add(sb.toString()); } return; } StringBuilder cur = new StringBuilder(); for (int i=index;i<s.length() && i-index < 3;i++) { cur.append(String.valueOf(s.substring(i,i+1))); if (Integer.valueOf(cur.toString()) <= 255) { sb.append(String.valueOf(s.substring(i,i+1))+"."); find(res,s,new StringBuilder(sb),count+1,i+1); sb.deleteCharAt(sb.length()-1); if (cur.charAt(0) == '0') { return; } } } } }

Last Update 2016.11.18