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.

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.

Test Cases

Input:

(string) s = "25525511135"

Output:

(string[]) ["255.255.11.135","255.255.111.35"]

Input:

(string) s = "101023"

Output:

(string[]) ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Solution

class Solution {
    public List<String> restoreIpAddresses(String s) {
        int n = s.length();
        List<String> res = new ArrayList<>();
        for(int i=0; i<n-2; i++) {
            for(int j=i+1; j<n-1; j++) {
                for(int k=j+1; k<n; k++) {
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k, n);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        res.add(s1+"."+s2+"."+s3+"."+s4);
                    }
                }
            }
        }
        return res;
    }

    private boolean isValid(String s) {
        if (s.length() == 0) return false;
        if (s.length() > 3) return false;
        if (s.charAt(0) == '0' && s.length() > 1) return false;
        if (Integer.parseInt(s) > 255) return false;
        return true;
    }
}
from typing import List


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res, n = [], len(s)
        for i in range(0, n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    s1, s2, s3, s4 = s[:i], s[i:j], s[j:k], s[k:]
                    if self.isValid([s1, s2, s3, s4]):
                        res.append(s1 + "." + s2 + "." + s3 + "." + s4)
        return res

    def isValid(self, li):
        valid = True
        for s in li:
            if len(s) == 0 or len(s) > 3 or (s[0] == '0' and len(s) > 1) or int(s) > 255:
                valid = False
                break
        return valid
Time Complexity: O(n3)
Space Complexity: O(1)