“This is the 39th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

93. Restore the IP address

The title

A valid IP address consists of four integers (each integer is between 0 and 255, and cannot contain a leading 0), separated by a hyphen (.).

  • For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “[email protected]” are invalid IP addresses.

Given a numeric string s to represent an IP address, return all possible valid IP addresses that can be formed by inserting a ‘.’ into s. You cannot reorder or delete any digits in s. You can return the answers in any order.

Example 1

Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"]Copy the code

Example 2

Input: s = "0000" Output: ["0.0.0.0"]Copy the code

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"]Copy the code

prompt

  • 1 <= s.length <= 20
  • sConsists only of numbers

Answer key

back

This topic is for reference

  • 46. The whole arrangement
  • 51. The N queens
  • 39. Sum of combinations

The above three problems can also be considered as recursive backtracking.

The following is the pseudo code for recursive backtracking

dfs();

function dfs(){
    if(Termination Conditions)return 
    
    for(All possible conditions for the current layer){if(Meet the required conditions){// Continue the recursion
            dfs()
        }
    }
}
Copy the code

According to the pseudo-code or the routine code, let’s introduce conditions to solve the problem;

The first step

  • Get the length of the string
  • Declare resultresultresult to store the answer
  • Write DFSDFSDFS
var restoreIpAddresses = function(s) { 
    const len = s.length
    const result = [];
    dfs();
    function dfs(){}};Copy the code

The second step

  • The DFSDFSDFS parameter requires two records, one for the IP that has been found, and one for the starting position needed to find the next IP
  • The IP that has been found is placed in the array, and the initial position of the next IP needs to be 0;
  • Path. length>4path.length >4path.length >4path.length >4
  • Path. length===4path.length ===4path.length ===4 A complete IP address may be found. Give up the rest
var restoreIpAddresses = function(s) { 
    const len = s.length
    const result = [];
    dfs(0[]);function dfs(level,path){
        if(path.length > 4) return;if (path.length === 4) return; }};Copy the code

The third step

  • For loop interval [1,4)[1,4] [1,4] because each IP has at most 3 bits;
  • Slicing string SSS from the starting position between [1,4)[1,4)[1,4);
  • Judge whether the string obtained by cutting meets the conditions, and continue to recurse if the conditions are met.
var restoreIpAddresses = function(s) { 
    const len = s.length
    const result = [];
    dfs(0[]);function dfs(level,path){
        if(path.length > 4) return;if (path.length === 4) return;
        
        for(let i = 1 ; i < 4 ; i++){
            const t = s.substring(level,level+i)
            
            if(check(t)){
                path.push(path)
                dfs(level+i,path)
                path.pop()
            }
            
        }
    }
    function check(string){}};Copy the code

conditions

  • The string cannot start with 0
  • The value cannot be larger than 225
  • A string that does not meet both criteria, discard recursion
function check(string) {

    if (string[0= = ='0' && string.length > 1) return false;
    if (Number(string) > 255) return false;
    return true;
 }
Copy the code

Edit the code as follows:

var restoreIpAddresses = function (s) {
  const len = s.length;
  const result = [];
  // DFS the first parameter represents the step value, and the second parameter stores the IP address
  dfs(0[]);return result;
  function dfs(level, path) {
    if (path.length > 4) return;
    if (path.length === 4 && level === len) {
      result.push(path.join('. '));
      return;
    }

    for (let i = 1; i < 4; i++) {
      if (level + i > len) return;
      const t = s.substring(level, level + i);
      if(check(t)) { path.push(t); dfs(level + i, path); path.pop(); }}}function check(string) {
    if (string[0= = ='0' && string.length > 1) return false;
    if (Number(string) > 255) return false;
    return true; }};Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section