93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.For example:Given "25525511135",return ["255.255.11.135", "255.255.111.35"]. (Order does
·
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135"
,
return ["255.255.11.135", "255.255.111.35"]
. (Order does not matter)
Subscribe to see which companies asked this question.
Solution:
Tips:
recursion, check the validation of the number.
Java Code:
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList();
if (s == null || s.length() < 4 || s.length() > 12) {
return result;
}
restoreIpAddresses(s, 0, "", 4, result);
return result;
}
public void restoreIpAddresses(String s, int begin, String curS, int ceil, List<String> result) {
//System.out.println("s = " + s + ", begin = " + begin + ", current s = " + curS + ", ceil = " + ceil);
if (begin > s.length()
|| s.length() - begin < ceil
|| s.length() - begin > ceil * 3) {
return;
}
if (ceil == 0) {
result.add(curS.substring(0, curS.length() - 1));
return;
}
// cut one char
restoreIpAddresses(s, begin + 1, curS + s.substring(begin, begin + 1) + ".", ceil - 1, result);
if (s.charAt(begin) != '0' && begin + 1 < s.length()) {
restoreIpAddresses(s, begin + 2, curS + s.substring(begin, begin + 2) + ".", ceil - 1, result);
if (begin + 2 < s.length() && Integer.valueOf(s.substring(begin, begin + 3)) <= 255) {
restoreIpAddresses(s, begin + 3, curS + s.substring(begin, begin + 3) + ".", ceil - 1, result);
}
}
}
}
更多推荐
已为社区贡献1条内容
所有评论(0)