leetcode: Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Solution and Precautions:
This one could be solved by backtracking (dfs). Basically we needo fill all the four positions as in A.B.C.D, every position A or B or C or D, could have at most three possible candidates, since no one could have a number of four digits. The candidate will be invalid because of
(1) there is a leading zero like 023;
(2) the range is not in 0 – 255 like 999
After all the positions are filled successfully, we got one possible ip address and add it into the final returned result.