Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given
Given
"25525511135",
return
Solution:["255.255.11.135", "255.255.111.35"]. (Order does not matter)DFS transformation question.
Be care of corner cases.
public class Solution {
public ArrayList restoreIpAddresses(String s) {
ArrayList result = new ArrayList();
if(s.length() < 4 || s.length() > 12)
return result;
helper(s, "", 0, result);
return result;
}
public void helper(String s, String str, int count, ArrayList result){
if(count == 3 && isValid(s)){
str += s;
result.add(str);
}
for(int i = 1; i <= 3; i++){
if (s.length() > i){
String tmp = s.substring(0,i);
if(isValid(tmp)){
helper(s.substring(i), str+tmp+".", count+1, result);
}
}
}
}
public boolean isValid(String str){
// check cases like "065"
if(str.charAt(0) == '0')
return str.equals("0");
return Integer.valueOf(str) >= 0 && Integer.valueOf(str) <= 255;
}
}
No comments:
Post a Comment