水贝网站建设/百度客服人工电话95188

恢复IP地址

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

样例

给出字符串 "25525511135"，所有可能的IP地址为：

["255.255.11.135","255.255.111.35"
]

（顺序无关紧要）

解题

深度优先遍历

注意：

1.中间IP位置不能以0开始，0.01.01.1非法，应该是0.0.101.1或者0.0.10.11

2.数不能大于255 

public class Solution {/*** @param s the IP string* @return All possible valid IP addresses* 不能包括01  001这样的格式*/public ArrayList<String> restoreIpAddresses(String s) {// Write your code hereArrayList<String> list = new ArrayList<String>();String IP="";int start = 0;int IPsize = 0;dfs(list,IP,s,start,IPsize);return list;}public void dfs(ArrayList<String> list,String IP,String s,int start,int IPsize){if(start == s.length()||IPsize>=4)return;if(IPsize == 3){String subIP = s.substring(start);if(isStartZero(subIP))return;if(!isLegal(subIP))return;IP+="." + subIP;if(!list.contains(IP))list.add(IP);return;}else{for(int i = start;i<s.length();i++){int j = 1;while(start+j<s.length() && j<=4){String subIP = s.substring(start,start+j);if(isStartZero(subIP))break;if(!isLegal(subIP))break;if(IPsize == 0){IP+=subIP;IPsize++;dfs(list,IP,s,start+j,IPsize);IP = "";}else{IP+="." + subIP;IPsize++;dfs(list,IP,s,start+j,IPsize);IP = IP.substring(0,IP.length() - j-1);}IPsize--;j++;}}}}public boolean isLegal(String subIP){Long numIP = Long.valueOf(subIP);if(numIP< 0 || numIP>255)return false;return true;}public boolean isStartZero(String subIP){if(subIP.substring(0,1).equals("0") && subIP.length() >=2)return true;return false;}
}