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 not matter)
Solution
DFS.
Code
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
dfs(s, new String(), 0, 0, res);
return res;
}
public void dfs(String s, String ip, int start, int step, List<String> res) {
if (step == 4 && start == s.length()) {
res.add(ip);
}
if (step == 4) return;
if(s.length()-start>(4-step)*3) return ;
if(s.length()-start<4-step) return ;
if (ip.length() != 0) ip+=".";
int num = 0;
for (int i = start; i < start + 3 && i < s.length(); ++i) {
num = num*10 + s.charAt(i) - '0';
if (num > 255) break;
ip += s.charAt(i);
dfs(s, ip, i + 1, step + 1, res);
if (num == 0) break;
}
}
}