Restore IP Addresses

Medium

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = "25525511135"

Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"

Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"

Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

1 <= s.length <= 20
s consists of digits only.

Solution

We want to apply our template backtracking1 to this problem. To fill in the logic:

is_leaf: start_index == len(s) and len(path) == 4`, when all of the digits are used and there are exactly 4 segments.
get_edges: the edges are the potential segments (of size 1-3) that starts at start_index.
is_valid: is the edge (integer) between 0 to 255? and does it not have a leading zero?

Implementation

def restoreIpAddresses(self, s: str) -> List[str]:
    def to_ip_address(path):
        address = path[0]
        for i in range(1, 4): address += "." + path[i]
        return address

    def get_edges(start_index):
        segments = []
        for i in range(start_index, start_index + 3):
            if i < len(s) :    # if not out of bound
                segments.append(s[start_index:i+1])  # up to and including s[i]
        return segments

    def is_valid(num):
        if num == "0": return True
        elif num[0] == "0": return False    # leading zero
        elif int(num) > 255: return False   # out of range
        else: return True

    def dfs(start_index, path):
        if len(path) > 4: return
        if start_index == len(s):   # if all digits are used
            if len(path) == 4:      # and there are exactly four segments
                ans.append(to_ip_address(path))     # add address to the result
            return
        for edge in get_edges(start_index):
            if is_valid(edge):
                path.append(edge)
                dfs(start_index + len(edge), path)
                path.pop()
    ans = []
    print(s[0:len(s)+1])
    dfs(0, [])
    return ans

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

Restore IP Addresses

Solution

Implementation

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Recommended Readings