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 ["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.

Tips and Divergent thinking:

N/A

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on May 23, 2013