Leetcode 93 recovery IP address

Ideas

Original link

1. In the main function , Count the length of the string len, Establish result set res, Path set path, Judge len Whether the length of the meets the requirements, i.e If more than 12 Or less than 4, be Go straight back to res, Because it doesn't conform to the specification
2. In the backtracking function , First set the termination conditions ： When begin When the starting position is the same as the length , also Remaining fields residue It's also 0, Will path Add to res In the middle and in the front , add ’.' Number
3. When i < begin + 3 When , if i >= len directly break. When the number of remaining fields *3 < len - i When , Indicates that the conditions are not met , At least it should be greater than or equal to
4. Then judge whether it is a legal address , if , Then intercept , Then join in path in , Then go to the backtracking function of the next layer , When entering the backtracking function ,begin The position of the should be i+1, instead of begin+ 1, Besides residue - 1, Finally remove
5. Judge IP Function with legal address ： First, count the length of the incoming string len, then When len>1 And the first position is 0 When , return false
6. Definition res Save results , Finally back to res Whether in 0-255 Between , namely [0,255]

class Solution { 
    

    public List<String> restoreIpAddresses(String s) { 
    
        int len = s.length();
        List<String> res = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        if(len < 4 || len > 12) return res;
        dfs(s, len, 0, 4, res, path);
        return res;
    }

    private void dfs(String s, int len, int begin, int residue, List<String> res, Deque<String> path){ 
    
        if(begin == len){ 
    
            if(residue == 0){ 
    
                res.add(String.join(".", path));
            }
            return;
        }
        for(int i = begin; i < begin + 3; i++){ 
    
            if(i >= len) break;
            if(residue * 3 < len - i){ 
    
                continue;
            }
            if(judgeIpSegment(s, begin, i)){ 
    
                String str = s.substring(begin, i + 1);
                path.addLast(str);
                dfs(s, len, i + 1, residue - 1, res, path);
                path.removeLast();
            }
        }
    }
    private boolean judgeIpSegment(String s, int left, int right){ 
    
        int len = right - left + 1;
        if(len > 1 && s.charAt(left) == '0'){ 
    
            return false;
        }
        int sum = 0;
        while(left <= right){ 
    
            sum = sum * 10 + s.charAt(left) - '0';
            left++;
        }
       return sum >=0 && sum <= 255;
    }
}

#####################################################################################################

class Solution { 
    

    public List<String> restoreIpAddresses(String s) { 
    
        int len = s.length();
        // First define the result set res
        List<String> res = new ArrayList<>();
        // Because the longest is 12  The shortest is 4
        if (len > 12 || len < 4) { 
    
            return res;
        }

        Deque<String> path = new ArrayDeque<>(4);
        dfs(s, len, 0, 4, path, res);
        return res;
    }

    //  You need a variable residue  Record how many remaining segments have not been split  
    private void dfs(String s, int len, int begin, int residue, Deque<String> path, List<String> res) { 
    
        // When the starting position 
        if (begin == len) { 
    
            if (residue == 0) { 
    
                // The series type is  String  Of   Construct the members of the collection , Where the specified separator is used between each member 
                res.add(String.join(".", path));
            }
            return;
        }
        //i < begin + 3 The meaning is ： Let it judge between three digits 
        for (int i = begin; i < begin + 3; i++) { 
    
            if (i >= len) { 
    
                break;
            }
        //len-i  Is the length of the remaining string ,residue Is the number of remaining segments , Maximum length of each section 3 position   namely  residue * 3, If its value is less than the remaining length , Indicates that the conditions are not met , At least it should be greater than or equal to , Because every paragraph is not necessarily 3 position 
            if (residue * 3 < len - i) { 
    
                continue;
            }

            if (judgeIpSegment(s, begin, i)) { 
    
                // If it's a legal field , Then intercept it and addLast Get into path
                String currentIpSegment = s.substring(begin, i + 1);
                path.addLast(currentIpSegment);
                // after , Because it operates on the same string , So will begin+1, Then subtract one... From the field 
                dfs(s, len, i + 1, residue - 1, path, res);
                path.removeLast();
            }
        }
    }

    private boolean judgeIpSegment(String s, int left, int right) { 
    
        int len = right - left + 1;
        /// When the first position is 0 When , At this time, the leading is 0, Not meeting the requirements 
        if (len > 1 && s.charAt(left) == '0') { 
    
            return false;
        }

        int res = 0;
        while (left <= right) { 
    
            // Keep counting   stay  left and right It's worth using res preservation 
            res = res * 10 + s.charAt(left) - '0';
            left++;
        }
        // Finally back to ,res Is it in 0-255 within 
        return res >= 0 && res <= 255;
    }
}