leetcode: Restore IP Addresses

Problem Description:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["", ""]. (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.

Written on May 23, 2013