public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
if (s == null || s.length() == 0) {
return result;
}
helper(result, new ArrayList<String>(), s, 0);
return result;
}
private void helper(List<String> result, List<String> path, String s, int start) {
if (start == s.length()) {
if (path.size() == 4) { //Attn!
result.add(String.join(".", path));
}
return;
}
for (int i = start; i < s.length(); i++) {
if (!isValid(s.substring(start, i + 1))) {
break;
}
if (path.size() == 3 && i + 1 != s.length()) {
continue;
}
path.add(s.substring(start, i + 1));
helper(result, path, s, i + 1);
path.remove(path.size() - 1);
}
}
private boolean isValid(String s) {
if (s.length() != Integer.toString(Integer.parseInt(s)).length()) {
return false; //Attn!
}
int i = Integer.parseInt(s);
return (i >= 0 && i <= 255);
}
}
2016年7月21日星期四
[LeetCode] #93 Restore IP Addresses
订阅:
博文评论 (Atom)
没有评论:
发表评论