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)
和上面一題的思想相同
public class Solution93 {
static LinkedList<LinkedList<String>> ans = new LinkedList<LinkedList<String>>();
public void restoreIpAddresses(String s, LinkedList<String> list3, int n) {
if (n > 4) {
return; //如果分段超過4端就不符合了
}
if (s == null || s.equals("*")) {
LinkedList<String> list1 = new LinkedList<>();
for (String string : list3) {
list1.add(string);
}
ans.add(list1);
return;
}
for (int i = 1; i < s.length(); i++) {
String str = s.substring(0, i);
if (isValid(str)) { //str是否符合理 比如2555就不合理
list3.add(str);
String res = s.substring(i, s.length());
restoreIpAddresses(res, list3, n + 1);
list3.pollLast();
}
}
}
private Boolean isValid(String str) {
if (str.length() > 3 || str.length() <= 0) {
return false;
}
int a = Integer.parseInt(str);
if (a <= 255 && a > 0) {
return true;
}
return false;
}
public static void main(String[] args) {
String s = "25525511135*";
LinkedList<String> list3 = new LinkedList<>();
new Solution93().restoreIpAddresses(s, list3, 0);
System.out.println(ans);
}
}
