Concise JavaScript solution using backtracking


  • 0
    var restoreIpAddresses = function(s) {
        if (s.length < 4 || s.length > 12) return [];
        const res = [];
        backtrack(res, s);
        return res;
    };
    
    function backtrack(res, s, curr = [], i = 0) {
        if (curr.length === 4) {
            res.push(curr.join('.'));
            return;
        }
        const charsLeft = s.length - i;
        const groupsLeft = 4 - curr.length;
        const minLen = groupsLeft === 1 ? charsLeft - groupsLeft + 1 : 1;
        const maxLen = s[i] === '0' ? 1 : Math.min(3, charsLeft - groupsLeft + 1);
        for (let len = minLen; len <= maxLen; len++) {
            let num = s.substr(i, len);
            if (num > 255) continue;
            curr.push(num);
            backtrack(res, s, curr, i + len);
            curr.pop();
        }
    }
    

    See here for my lookup table solution.


Log in to reply
 

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