1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 16, 2015
4+ Problem: Restore IP Addresses
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/restore-ip-addresses/
7+ Notes:
8+ Given a string containing only digits, restore it by returning all possible valid IP address combinations.
9+ For example:
10+ Given "25525511135",
11+ return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
12+
13+ Solution: DFS.
14+ */
15+ public class Solution {
16+ public List <String >restoreIpAddresses (String s ) {
17+ List <String >res =new ArrayList <String >();
18+ dfs (s ,new String (),0 ,0 ,res );
19+ return res ;
20+ }
21+ public void dfs (String s ,String ip ,int start ,int step ,List <String >res ) {
22+ if (step ==4 &&start ==s .length ()) {
23+ res .add (ip );
24+ }
25+ if (step ==4 )return ;
26+ if (s .length ()-start >(4 -step )*3 )return ;
27+ if (s .length ()-start <4 -step )return ;
28+ if (ip .length () !=0 )ip +="." ;
29+ int num =0 ;
30+ for (int i =start ;i <start +3 &&i <s .length (); ++i ) {
31+ num =num *10 +s .charAt (i ) -'0' ;
32+ if (num >255 )break ;
33+ ip +=s .charAt (i );
34+ dfs (s ,ip ,i +1 ,step +1 ,res );
35+ if (num ==0 )break ;
36+ }
37+ }
38+ }
