Formatted question description: https://leetcode.ca/all/93.html
93 Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
For the segmentation problem of character strings, add three dots to the input character string and divide the character string into four segments. Each segment must be legal. Seek all possible situations.
Based on so many questions so far, two experiences have been drawn.
- One is that as long as the subsequence or registration problem of a string is encountered, the
dynamic programmingDP is first considered;
- the other is that as long as all possible situations need to be requested,
recursionis first considered.
This question is not a question of seeking a subsequence or registration of a string, but more in line with the second case, so we have to use recursion to solve it.
We use k to represent the number of segments that still need to be divided. If k = 0, it means that three points have been added and four segments have been formed. If the string is just empty at this time, the current divided result will be saved. If k != 0, then for each segment, we use one, two, and three digits to try and judge whether it is legal or not. If it is legal, call recursion to continue dividing the remaining strings, and finally sum All legal combinations