93. Restore IP Addresses

Description

Given a string s containing only digits. Return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single points and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "[email protected]" are invalid IP addresses.

Constraints

• 0 <= s.length <= 3000

• s consists of digits only.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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 = "1111"

Output: ["1.1.1.1"]

Example 4

Input: s = "010010"

Output: ["0.10.0.10", "0.100.1.0"]

Example 5

Input: s = "101023"

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> resultList = new ArrayList<>();
        int n = s.length();
        if(n < 4 || n > 12) return resultList;
        for(int p = 1; p < 4; p++) {
            for(int q = 1; q < 4; q++) {
                for(int r = 1; r < 4; r++) {
                    for(int t = 1; t < 4; t++) {
                        if(p+q+r+t == n) {
                            int v1 = Integer.parseInt(s.substring(0, p));
                            if(v1 > 255) continue;
                            
                            int v2 = Integer.parseInt(s.substring(p, p+q));
                            if(v2 > 255) continue;
                            
                            int v3 = Integer.parseInt(s.substring(p+q, p+q+r));
                            if(v3 > 255) continue;
                            
                            int v4 = Integer.parseInt(s.substring(p+q+r));
                            if(v4 > 255) continue;
                            
                            String value = v1 + "." + v2 + "." + v3 + "." + v4;
                            if(value.length() == n+3) {
                                resultList.add(value);
                            }
                        }
                    }
                }
            }
        }
        return resultList;
    }
}

Follow up