Leetcode P93 Java使用DFS解决_dfs算法 leetcode java

Leetcode P93 Java使用DFS解决

ideas

首先我们创建一个集合用来保存我们的返回数据

    private List<String> res = new ArrayList<>();
1

接下来我们编写dfs算法

/**
 *
 * @param s
 * @param index  当前的起始下标
 * @param cur    现在操作的字符串保存的ip内容
 * @param number 小数点的个数
 */
public void dfs(String s, int index, String cur,int number)
1
2
3
4
5
6
7
8

编写剪枝个数

        //减去枝叶
        if (index > s.length() || number > 4){
            return;
        }
        //满足要求保存数据
        if (number == 4 && index == s.length()) {
            res.add(cur);
            return;
        }
1
2
3
4
5
6
7
8
9

如果我们的子网段的长度大于等于2，那么就判断是否已0前导，如果是则直接return不合法

            String tmp = s.substring(index,i+1);
            //查看是否为0-256之间
            int num = Integer.valueOf(tmp);
            //查看是否0前导
            if (i+1 - index >= 2){
                if (s.charAt(index) == '0') {
                    return;
                }
            }
1
2
3
4
5
6
7
8
9

如果我们子网段的数字在[0,255]区间，那么就是合法字段，则起始下标移动，如果不是则不合法

            if (num >= 0 && num < 256){
                dfs(s,i+1,number ==3 ? cur+num : cur+num+".",number+1);
            }else{
                return;
            }
1
2
3
4
5

code

class Solution {
    private List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s,0,"",0);
        return res;
    }

    public void dfs(String s, int index, String cur,int number){
        //减去枝叶
        if (index > s.length() || number > 4){
            return;
        }
        //满足要求
        if (number == 4 && index == s.length()) {
            res.add(cur);
            return;
        }

        for (int i = index; i < s.length(); i++) {
            String tmp = s.substring(index,i+1);
            //查看是否为0-256之间
            int num = Integer.valueOf(tmp);
            //查看是否0前导
            if (i+1 - index >= 2){
                if (s.charAt(index) == '0') {
                    return;
                }
            }
            //合法字段
            if (num >= 0 && num < 256){
                dfs(s,i+1,number ==3 ? cur+num : cur+num+".",number+1);
            }else{
                return;
            }
        }
    }
}
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