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)
This problem can be solved by bfs method
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 |
public
class
Solution { public
ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> result = new
ArrayList<String>(); int
len = s.length(); if(len >= 4
&& len <= 12){ result = bfs(s); } return
result; } public
ArrayList<String> bfs(String s){ ArrayList<String> result = new
ArrayList<String>(); Queue<PairStrings> tempResult = new
LinkedList<PairStrings>(); tempResult.add(new
PairStrings("", s)); for(int
i = 0; i < 4; ++i){ Queue<PairStrings> temp = new
LinkedList<PairStrings>(); while(tempResult.peek() != null){ PairStrings aPair = tempResult.poll(); String aString = aPair.s2; int
len = aString.length(); if(len > 0){ for(int
j = 1; j < 4
&& j < len + 1; ++j){ String subs = aString.substring(0,j); if((len - j <= 3
* ( 3
- i)) && checkValidation(subs)){ PairStrings newPair = new
PairStrings(aPair.s1 + "."
+ subs, aString.substring(j, len)); temp.add(newPair); } } } } tempResult = temp; } while(tempResult.peek() != null){ PairStrings finalPairs = tempResult.poll(); String finalString = finalPairs.s1; if(finalString.charAt(0) == ‘.‘) result.add(finalString.substring(1, finalString.length())); } return
result; } public
boolean
checkValidation(String s){ boolean
canAppend = false; if(s.length() != 0){ if(s.charAt(0) == ‘0‘) canAppend = (s.equals("0")); else{ int
num = Integer.parseInt(s); canAppend = (num >= 0
&& num <= 255); } } return
canAppend; }}class
PairStrings{ String s1; String s2; PairStrings(String s1, String s2){ this.s1 = s1; this.s2 = s2; }} |
leetcode--Restore IP Addresses,布布扣,bubuko.com
leetcode--Restore IP Addresses
原文：http://www.cnblogs.com/averillzheng/p/3617073.html