93. Restore IP Addresses

[Tcdian]

93. Restore IP Addresses

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

Example

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const addressFragment = [];
    const result = [];
    backtracking(0);
    return result;

    function backtracking(index) {
        if (addressFragment.length === 4) {
            if (index === s.length) {
                result.push(addressFragment.join('.'));
            }
            return;
        }
        for (let i = index; i < s.length; i++) {
            const fragment = s.slice(index, i + 1);
            if (isIpFragment(fragment)) {
                addressFragment.push(fragment);
                backtracking(i + 1);
                addressFragment.pop();
            }
        }
    }
    function isIpFragment(fragment) {
        if (fragment.length !== 1 && fragment.startsWith('0')) {
            return false;
        }
        return Number(fragment) <= 255;
    }
};

• TypeScript Solution

function restoreIpAddresses(s: string): string[] {
    const addressFragment: string[] = [];
    const result: string[] = [];
    backtracking(0);
    return result;

    function backtracking(index: number) {
        if (addressFragment.length === 4) {
            if (index === s.length) {
                result.push(addressFragment.join('.'));
            }
            return;
        }
        for (let i = index; i < s.length; i++) {
            const fragment = s.slice(index, i + 1);
            if (isIpFragment(fragment)) {
                addressFragment.push(fragment);
                backtracking(i + 1);
                addressFragment.pop();
            }
        }
    }
    function isIpFragment(fragment: string) {
        if (fragment.length !== 1 && fragment.startsWith('0')) {
            return false;
        }
        return Number(fragment) <= 255;
    }
};