leetcode/javascript/0093-restore-ip-addresses.js at main · AlexS778/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    let res = [];

    if (s.length > 12) return res;

    /**
     *
     * @param {number} i
     * @param {number} dots
     * @param {string} currentIP
     */
    function backtracking(i, dots, currentIP) {
        if (dots === 4 && i == s.length) {
            res.push(currentIP.slice(0, currentIP.length - 1));
            return;
        } else if (dots > 4) {
            return;
        }

        for (let j = i; j < Math.min(i + 3, s.length); j++) {
            if (+s.slice(i, j + 1) < 256 && (i == j || s[i] != '0')) {
                backtracking(
                    j + 1,
                    dots + 1,
                    currentIP + s.slice(i, j + 1) + '.'
                );
            }
        }
    }

    backtracking(0, 0, '');

    return res;
};