JavaScript solution using lookup table and regex


  • 0

    Obviously I tried to find any excuse to use regular expressions :). The idea is to do a regex match over all possible groups for the input string length. The regex looks like ^(group1)(group2)(group3)(group4)$ and each group's regex is taken from r depending on the number of digits specified by a permutation in perms.

    var restoreIpAddresses = function(s) {
        if (s.length < 4 || s.length > 12) return [];
        const perms = {
            '4': [[1,1,1,1]],
            '5': [[2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2]],
            '6': [[3,1,1,1], [1,3,1,1], [1,1,3,1], [1,1,1,3], [2,2,1,1], [2,1,2,1], [2,1,1,2], [1,2,2,1], [1,2,1,2], [1,1,2,2]],
            '7': [[3,2,1,1], [3,1,2,1], [3,1,1,2], [1,3,2,1], [1,3,1,2], [1,1,3,2], [2,3,1,1], [2,1,3,1], [2,1,1,3], [1,2,3,1],
                  [1,2,1,3], [1,1,2,3], [2,2,2,1], [2,2,1,2], [2,1,2,2], [1,2,2,2]],
            '8': [[3,3,1,1], [3,1,3,1], [3,1,1,3], [1,3,3,1], [1,3,1,3], [1,1,3,3], [2,2,3,1], [2,3,2,1], [2,3,1,2], [3,2,2,1],
                  [3,2,1,2], [3,1,2,2], [2,2,1,3], [2,1,2,3], [2,1,3,2], [1,2,2,3], [1,2,3,2], [1,3,2,2], [2,2,2,2]]
        };
        for (let i = 9; i <= 12; i++) {
            perms[i] = perms[16 - i].map(p => p.map(a => a === 3 ? 1 : a === 1 ? 3 : 2));
        }
        const r = ['', '\\d', '[1-9]\\d', '1\\d\\d|2(?:[0-4]\\d|5[0-5])'];
        const res = [];
        for (let c of perms[s.length]) {
            let ip = s.replace(new RegExp(`^(${r[c[0]]})(${r[c[1]]})(${r[c[2]]})(${r[c[3]]})$`), '$1.$2.$3.$4');
            if (ip.length > s.length) res.push(ip);
        }
        return res;
    };
    

    Precomputing the entire lookup table and precompiling the regular expressions gives a speed boost (beats 60% improved from 7%):

    const perms = {
        '4' : [[1,1,1,1]],
        '5' : [[2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2]],
        '6' : [[3,1,1,1], [1,3,1,1], [1,1,3,1], [1,1,1,3], [2,2,1,1], [2,1,2,1], [2,1,1,2], [1,2,2,1], [1,2,1,2], [1,1,2,2]],
        '7' : [[3,2,1,1], [3,1,2,1], [3,1,1,2], [1,3,2,1], [1,3,1,2], [1,1,3,2], [2,3,1,1], [2,1,3,1], [2,1,1,3], [1,2,3,1],
               [1,2,1,3], [1,1,2,3], [2,2,2,1], [2,2,1,2], [2,1,2,2], [1,2,2,2]],
        '8' : [[3,3,1,1], [3,1,3,1], [3,1,1,3], [1,3,3,1], [1,3,1,3], [1,1,3,3], [2,2,3,1], [2,3,2,1], [2,3,1,2], [3,2,2,1],
               [3,2,1,2], [3,1,2,2], [2,2,1,3], [2,1,2,3], [2,1,3,2], [1,2,2,3], [1,2,3,2], [1,3,2,2], [2,2,2,2]],
        '9' : [[3,3,2,1], [3,2,3,1], [3,2,1,3], [2,3,3,1], [2,3,1,3], [2,1,3,3], [3,3,1,2], [3,1,3,2], [3,1,2,3], [1,3,3,2],
               [1,3,2,3], [1,2,3,3], [3,2,2,2], [2,3,2,2], [2,2,3,2], [2,2,2,3]],
        '10': [[3,3,3,1], [3,3,1,3], [3,1,3,3], [1,3,3,3], [3,3,2,2], [3,2,3,2], [3,2,2,3], [2,3,3,2], [2,3,2,3], [2,2,3,3]],
        '11': [[3,3,3,2], [3,3,2,3], [3,2,3,3], [2,3,3,3]],
        '12': [[3,3,3,3]]
    };
    const r = ['', '\\d', '[1-9]\\d', '1\\d\\d|2(?:[0-4]\\d|5[0-5])'];
    for (let len in perms) {
        for (let i = 0; i < perms[len].length; i++) {
            perms[len][i] = new RegExp('^(' + perms[len][i].map(n => r[n]).join(')(') + ')$');
        }
    }
    
    var restoreIpAddresses = function(s) {
        if (!perms[s.length]) return [];
        const res = [];
        for (let re of perms[s.length]) {
            let ip = s.replace(re, '$1.$2.$3.$4');
            if (ip.length > s.length) res.push(ip);
        }
        return res;
    };
    

    I'm unsure about regex time complexity but assume that the simple regexes here are comparable to character-by-character comparison.

    Since n ≤ 12 for valid IPs there is an argument for constant time and/or space complexity, but obviously if we could extend the definition of IPs for longer strings then the complexity would still depend on the input size (see permutations of multisets where the set size is the number of IP sections).

    Here is what the final collection of regexes looks like, with no apparent speed advantage in this form:

    const perms = {
        '4': [ /^(\d)(\d)(\d)(\d)$/ ],
        '5': [
            /^([1-9]\d)(\d)(\d)(\d)$/,
            /^(\d)([1-9]\d)(\d)(\d)$/,
            /^(\d)(\d)([1-9]\d)(\d)$/,
            /^(\d)(\d)(\d)([1-9]\d)$/
        ],
        '6': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)(\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)$/,
            /^(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(\d)(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)([1-9]\d)(\d)(\d)$/,
            /^([1-9]\d)(\d)([1-9]\d)(\d)$/,
            /^([1-9]\d)(\d)(\d)([1-9]\d)$/,
            /^(\d)([1-9]\d)([1-9]\d)(\d)$/,
            /^(\d)([1-9]\d)(\d)([1-9]\d)$/,
            /^(\d)(\d)([1-9]\d)([1-9]\d)$/
        ],
        '7': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)([1-9]\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)$/,
            /^(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)$/,
            /^([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^([1-9]\d)(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(\d)([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)([1-9]\d)([1-9]\d)(\d)$/,
            /^([1-9]\d)([1-9]\d)(\d)([1-9]\d)$/,
            /^([1-9]\d)(\d)([1-9]\d)([1-9]\d)$/,
            /^(\d)([1-9]\d)([1-9]\d)([1-9]\d)$/
        ],
        '8': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)([1-9]\d)$/,
            /^([1-9]\d)([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(\d)([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)$/,
            /^([1-9]\d)([1-9]\d)([1-9]\d)([1-9]\d)$/
        ],
        '9': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)([1-9]\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)$/,
            /^([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^([1-9]\d)([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/
        ],
        '10': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/
        ],
        '11': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/,
            /^([1-9]\d)(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/
        ],
        '12': [
            /^(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))(1\d\d|2(?:[0-4]\d|5[0-5]))$/
        ]
    };
    

    FWIW the non-regex version offers no speed improvement:

    const perms = {
        '4' : [[1,1,1,1]],
        '5' : [[2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2]],
        '6' : [[3,1,1,1], [1,3,1,1], [1,1,3,1], [1,1,1,3], [2,2,1,1], [2,1,2,1], [2,1,1,2], [1,2,2,1], [1,2,1,2], [1,1,2,2]],
        '7' : [[3,2,1,1], [3,1,2,1], [3,1,1,2], [1,3,2,1], [1,3,1,2], [1,1,3,2], [2,3,1,1], [2,1,3,1], [2,1,1,3], [1,2,3,1],
               [1,2,1,3], [1,1,2,3], [2,2,2,1], [2,2,1,2], [2,1,2,2], [1,2,2,2]],
        '8' : [[3,3,1,1], [3,1,3,1], [3,1,1,3], [1,3,3,1], [1,3,1,3], [1,1,3,3], [2,2,3,1], [2,3,2,1], [2,3,1,2], [3,2,2,1],
               [3,2,1,2], [3,1,2,2], [2,2,1,3], [2,1,2,3], [2,1,3,2], [1,2,2,3], [1,2,3,2], [1,3,2,2], [2,2,2,2]],
        '9' : [[3,3,2,1], [3,2,3,1], [3,2,1,3], [2,3,3,1], [2,3,1,3], [2,1,3,3], [3,3,1,2], [3,1,3,2], [3,1,2,3], [1,3,3,2],
               [1,3,2,3], [1,2,3,3], [3,2,2,2], [2,3,2,2], [2,2,3,2], [2,2,2,3]],
        '10': [[3,3,3,1], [3,3,1,3], [3,1,3,3], [1,3,3,3], [3,3,2,2], [3,2,3,2], [3,2,2,3], [2,3,3,2], [2,3,2,3], [2,2,3,3]],
        '11': [[3,3,3,2], [3,3,2,3], [3,2,3,3], [2,3,3,3]],
        '12': [[3,3,3,3]]
    };
    
    var restoreIpAddresses = function(s) {
        if (!perms[s.length]) return [];
        const res = [];
        for (let p of perms[s.length]) {
            let a = s.substr(0, p[0]);
            let b = s.substr(p[0], p[1]);
            let c = s.substr(p[0] + p[1], p[2]);
            let d = s.substr(p[0] + p[1] + p[2], p[3]);
            if (a[1] && a[0] === '0' || a > 255 || b[1] && b[0] === '0' || b > 255
             || c[1] && c[0] === '0' || c > 255 || d[1] && d[0] === '0' || d > 255) continue;
            let ip = `${a}.${b}.${c}.${d}`;
            if (ip.length === s.length + 3) res.push(ip);
        }
        return res;
    };
    

    See here for my backtracking solution which isn't any faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.