【LeetCode】93. Restore IP Addresses
原題
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
：
： ， IP ， 。
：
1) for
2) ✔
public static List restoreIpAddresses(String s) {
List result = new ArrayList<>();
int[] splitPosition = new int[5];
splitPosition[4] = s.length();
back(s, splitPosition, 0, result);
return result;
}
public static void back(String s, int[] splitPosition, int numOfJoin, List result)
{
if(numOfJoin == 3)
{
if(splitPosition[3] >= s.length()) return;
if(s.length() - splitPosition[3] > 3) return;
String ip = "";
for(int i = 0; i < 4; i++)
{
String temp = s.substring(splitPosition[i], splitPosition[i+1]);
if(temp.length() > 1 && temp.startsWith("0")) return;
int tempNum = Integer.parseInt(temp);
if(tempNum < 0 || tempNum > 255) return;
ip += i == 3 ? temp : temp + ".";
}
result.add(ip);
return;
}
for(int i = 1; i <= 3; i++)
{
splitPosition[numOfJoin + 1] = splitPosition[numOfJoin] + i;
back(s, splitPosition,numOfJoin+1, result);
splitPosition[numOfJoin + 1] = 0;
}
}