Leetcode 93 recover ip address
A valid IP address consists of exactly four integers (each between 0 and 255, without leading zeros), separated by '.'.
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 string s containing only numbers representing an IP address, return all possible valid IP addresses which can be formed by inserting '.' in s.You cannot reorder or delete any numbers in s.You can return answers in any order.
Link: https://leetcode.cn/problems/restore-ip-addresses
Solution ideas:
Use the backtracking method
Termination conditions: ①When the segment is full of 4 segments or ②The string has been allocated
If ①② is satisfied, it meansThe IP is valid, add it to the result set, and then return
If only one of the two is satisfied, it means the IP is invalid, and return directly
Single-level recursion: To judge how to divide a segment, enterParameter (string s, start position of the segment, number of segments already divided)
Determine whether a segment is legal (length, value size, whether the first position is 0)
① Segment length (i + 1 - start)<= 3
②The size of the value is in the range of [0,255]
③If the length of the paragraph is greater than 1 and the beginning of the paragraph is 0
After judging, add the paragraph, and then judge whether it is necessary to add a decimal point, it has been divided into paragraphsNumber ++ to enter the next subsection recursively
Cancel the operation of adding subsections, the number of subsections --, when judging whether the decimal point needs to be deleted, delete the subsection
class Solution {List res = new LinkedList<>();StringBuilder path = new StringBuilder();public List restoreIpAddresses(String s) {dfs(s, 0, 0);return res;}private void dfs(String s, int start, int number) {// Termination conditionif (number == 4 && start == s.length()) {res.add(path.toString());return;}if (number == 4 || start == s.length()) {return;}// single level recursionfor (int i = start; i < s.length(); i++) {if (i - start >= 3) {break;}if (Integer.parseInt(s.substring(start, i + 1)) < 0 || Integer.parseInt(s.substring(start, i + 1)) > 255) {break;}if (i > start && s.charAt(start) == '0') {break;}// processing logicpath.append(s.substring(start, i + 1));number++;if (number <= 3) {path.append(".");}// recursedfs(s, i + 1, number);// cancel processingif (number <= 3) {path.deleteCharAt(path.length() - 1);}number--;path.delete(path.length() - (i - start + 1), path.length());}}} 
