Commit2a4ee69

applewjg

committed

RestoreIPAddresses

Change-Id: Ifa17bc99b1af5975a1901ca3eb45bb06f2f2cf34

1 parenta19efc3 commit2a4ee69Copy full SHA for 2a4ee69

File tree

+38

-0

lines changed

+38

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`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`	`+publicclassSolution {`
	`16`	`+publicList<String>restoreIpAddresses(Strings) {`
	`17`	`+List<String>res =newArrayList<String>();`
	`18`	`+dfs(s,newString(),0,0,res);`
	`19`	`+returnres;`
	`20`	`+ }`
	`21`	`+publicvoiddfs(Strings,Stringip,intstart,intstep,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`	`+intnum =0;`
	`30`	`+for (inti =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`	`+}`

Comments

(0)