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)
Solution: 注意各种条件: 1.0后面不能再接数,2.点不能加在最后,3.3个点的才正确
public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() < 4) {
return ans;
}
helper(s, 0, 0, new StringBuilder(), ans, 0);
return ans;
}
private void helper(String s, int index, int sum, StringBuilder path, List<String> ans, int count_of_dot) {
if (index == s.length()) {
if (count_of_dot == 3) {
ans.add(path.toString());
}
return;
}
sum = sum * 10 + s.charAt(index) - '0';
if (sum > 255) {
return;
}
path.append(s.charAt(index));
if (sum > 0 || sum == 0 && index == s.length() - 1) {
helper(s, index + 1, sum, path, ans, count_of_dot);
}
if (count_of_dot < 3 && index < s.length() - 1) {
path.append('.');
helper(s, index + 1, 0, path, ans, count_of_dot + 1);
path.deleteCharAt(path.length() - 1);
}
path.deleteCharAt(path.length() - 1);
}