LeetCode_ 93_ Restore IP address

Topic link

• https://leetcode.cn/problems/restore-ip-addresses/

Title Description

It works IP Address It's just four integers （ Each integer is located in 0 To 255 Between the composition of , And it can't contain leading 0）, Use... Between integers ‘.’ Separate .

• for example ："0.1.2.201" and "192.168.1.1" yes It works IP Address , however "0.011.255.245"、"192.168.1.312" and "[email protected]" yes Invalid IP Address .

Given a string containing only numbers s , It is used to indicate a IP Address , Return all possible It works IP Address , These addresses can be accessed through s Insert '.' To form . you You can't Reorder or delete s Any number in . You can press whatever Return the answers in order .

Example 1：

 Input ：s = "25525511135"
 Output ：["255.255.11.135","255.255.111.35"]

Example 2：

 Input ：s = "0000"
 Output ：["0.0.0.0"]

Example 3：

 Input ：s = "101023"
 Output ：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Tips ：

• 1 <= s.length <= 20
• s It's just numbers

Their thinking

Retrospective recursive trilogy

• Parameters and return values of recursive functions
  • s: character string
  • startIndex: control for loop
  • pointNum: Indicates the number of commas , It has been used to record several paragraphs
  • ans： Set of qualified results
• Termination condition of recursive function
  • When pointNum == 3 It indicates that the string has been divided into 4 paragraph , It's in line with IP The rules of address
  • Then verify whether the fourth paragraph is legal , If it's legal, add it to the result set
• Single layer logic
  • [startIndex,i] This interval is the substring intercepted , You need to judge whether this substring is legal , If it is legal, add a match after the string . Indicates that it has been divided
  • If it is not legal, end this layer cycle

Judge the legitimacy of substring

• Duan Weiyi 0 The number beginning with bit is illegal
• It is illegal to have negative integer characters in the segment
• If it is greater than 255 It is illegal.
• Other situations are legal

AC Code

class Solution {
    
    public List<String> restoreIpAddresses(String s) {
    
 List<String> ans = new ArrayList<>();
        backTracing(s, 0, 0, ans);
        return ans;
    }

    private static void backTracing(String s, int startIndex, int pointNum, List<String> ans) {
    
        // Termination conditions 
        if (pointNum == 3) {
    
            if (isValid(s, startIndex, s.length() - 1)) {
    
                ans.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
    
            if (isValid(s, startIndex, i)) {
    
                // stay str Add a point after 
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;
                backTracing(s, i + 2, pointNum, ans);
                pointNum--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            } else {
    
                break;
            }
        }
    }

    private static boolean isValid(String s, int start, int end) {
    
        if (start > end) {
    
            return false;
        }
        // Leading 0 The number of is illegal 
        if (s.charAt(start) == '0' && start != end) {
    
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
    
            if (s.charAt(i) > '9' || s.charAt(i) < '0') {
    
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) {
    
                return false;
            }
        }
        return true;
    }
}