Valid Ip Addresses InterviewBit Solution
Problem: Valid Ip Addresses
Problem Description:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
A valid IP address must be in the form of A.B.C.D, where A, B, C and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.
Example:
Given “25525511135”,
return [“255.255.11.135”, “255.255.111.35”]. (Make sure the returned strings are sorted in order)
Solution Approach:
Brute Force will work, you just have to insert 3 dots in between the string.
Time Complexity:
Since after each character we can either insert a dot or not. So we have two options for N characters, therefore time complexity is O(2^N).
