[LeetCode] 93. Restore IP Addresses

😎풀이

백트레킹 문제이다.

IP 주소의 기본 구성을 잘 모른다 하더라도 친절히 적합한 IP 주소의 요건을 문제에서 제시하기에 큰 어려움 없이 풀이가 가능하다

function restoreIpAddresses(s: string): string[] {
    // 4자 미만이거나 12자를 초과하는 경우 생성 불가
    const len = s.length;
    if(len < 4 || len > 12) return [];

    const result = []

    // 백트레킹
    // start: ip 시작 인덱스
    // dots: 현재 포함된 '.' 수
    // currentIP: 현재까지 만들어진 ip주소
    function backTracking(start: number, dots: number, currentIP: string): void {
        // IP 주소가 완성되는 단계라면
        if(dots === 3) {
            // 남은 문자열 다 확보
            const curStr = s.slice(start);
            if(!isValidIP(curStr)) return;
            const ip = currentIP + curStr;

            result.push(ip);
            return;
        }

        // 문자열 최대길이 내에서 순회
        for(let i = 1; i <= 3 && (start + i) <= 12; i++) {
            // 현재 문자열 + '.'
            const curStr = s.slice(start, start + i);
            if(!isValidIP(curStr)) continue;
            backTracking(start + i, dots + 1, currentIP + curStr + '.')
        }
    }

    // IP에 적합한지 판단하는 함수
    function isValidIP(ip: string): boolean {
        // 빈 문자열 안됨
        if(ip.length === 0) return false;
        // 0으로 시작하면 안됨
        if(ip.length > 1 && ip[0] === '0') return false;
        // 숫자 범위는 0과 255 사이에 위치해야함
        const intIP = Number(ip)
        if(intIP < 0 || intIP > 255) return false;

        return true;
    }

    backTracking(0, 0, '')
    return result
};