Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities
## Numeric string is converted to IP address
Problem description
You now have a string containing only numbers, and convert the string to an IP address that returns all possible cases.
Note: an IP address is a sequence of four digits in the format of “X.X.X.X”, where x is in the range of [0,255].
Example:
Input: “25525522135”
Output: [“255.255.22.135”, “255.255.221.35”]
To analyze problems
We all know that an IP address is made up of four digits, with the character “. Make a connection. To convert a numeric string to an IP address, you use four “s. Divide it into four parts, each with a numeric range of [0,255].
According to the requirements of the topic, since we need to find out all possible IP addresses, we choose to use backtracking algorithm to solve, find out all possible string segmentation methods, and screen out the way that meets the requirements of IP addresses.
Backtracking algorithms are implemented recursively, so we first define the recursive function DFS (count, start), which means that we are searching for the count segment of the IP address starting from s[start] (assuming the given numeric string is S), because there are four segments of IP address. So count ∈ {0,1,2,3}. For each segment of the IP address, the range is [0,255], because we enumerate the current segment of the IP address from start to end. If the number s[start, end] is in the range of [0,255], we perform DFS (count+1, end+1) for the next segment of the IP address search. If s[start] is 0, the IP address must be 0.
During the search, if all four IP addresses have been obtained and the entire string has been traversed, it means that we have found a restored IP address and added it to the result. Let’s look at the splitting of string “25525522135”.
Let’s look at the implementation of the code.
class Solution: def restoreIpAddresses(self, s): Segments =[0] * ip_count () def DFS (count, start): If count == ip_count: if start == len(s): Res.append (".". Join (STR (seg) for seg in segments)) return # start == len(s): If s[start]=="0", return # if s[start]=="0", return # if s[start]=="0" : Segments [start] =0 DFS (count + 1, start + 1) =0 DFS (count + 1, start + 1) Addr = addr * 10 + (ord(s[end]) -ord ("0")) DFS (count + 1, end + 1) else: Return ress =Solution() print(s.restroipaddresses ("25525522135"))Copy the code