FilesExpand file tree

 master

/

RestoreIpAddresses.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (44 loc) · 1.51 KB

 master

/

RestoreIpAddresses.java

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (44 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package Algorithms.string;

import java.util.ArrayList;

import java.util.List;

public class RestoreIpAddresses {

public List<String> restoreIpAddresses(String s) {

if (s == null) {

return null;

}

ArrayList<String> ret = new ArrayList<String>();

ArrayList<String> path = new ArrayList<String>();

dfs(s, 0, path, ret);

return ret;

}

public void dfs(String s, int index, ArrayList<String> path, ArrayList<String> ret) {

if (path.size() == 4) {

if (index == s.length()) {

StringBuilder sb = new StringBuilder();

for (String str: path) {

sb.append(str);

sb.append('.');

}

sb.deleteCharAt(sb.length() - 1);

ret.add(sb.toString());

}

return;

}

int len = s.length();

for (int i = index; i < index + 3 && i < len; i++) {

// 不可以有005这样子的IP地址。

if (s.charAt(index) == '0' && i > index) {

break;

}

String pre = s.substring(index, i + 1);

// 过滤num > 255的情况。

int num = Integer.parseInt(pre);

if (num > 255) {

continue;

}

path.add(pre);

dfs(s, i + 1, path, ret);

path.remove(path.size() - 1);

}

}

}