LeetCode Restore IP Addresses (JavaScript), DFS

링크 : https://leetcode.com/problems/restore-ip-addresses/description/

문제 설명

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

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

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 1 <= s.length <= 20
• s consists of digits only.

---

문제 풀이

접근 방식

• dfs 함수 인자
  • ip : 현재 저장된 ip 문자열
  • index : 현재 검사할 s의 index
  • part : .의 갯수 (총 4개의 파트로 구성됨)
• dfs 로직
  1. part가 4인 경우 4개의 파트로 ip 구성이 되었으므로 index가 LENGTH와 같다면 answer에 추가 (맞는 ip)
  2. ip를 만들 수 있는 경우의 수 (최대 3개)
     1. 현재 index를 기준으로 최대 3개까지 설정 가능
        • 2글자 이상인 경우 시작이 0이 아니여야 함
        • 0 ~ 255 사이의 숫자 값으로 되어 있어야 함
     2. 다음 ip를 넘겨줄 때 첫 번째 part(맨 앞 부분의 숫자)가 아니라면 . 을 추가해 ip로 넘겨줌

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const LENGTH = s.length;
    const answer = [];

    const dfs = (ip, index, part) => {
        if (part === 4) {
            if (index === LENGTH) {
                answer.push(ip);
            }
            return;
        }

        for (let len = 1; len <= 3; len++) {
            const nextIndex = index + len;
            if (nextIndex > LENGTH) break;

            const word = s.slice(index, nextIndex);

            if (word.length > 1 && word[0] === '0') continue;
            if (parseInt(word) > 255) continue;

            const nextIp = part === 0 ? word : `${ip}.${word}`;
            dfs(nextIp, nextIndex, part + 1);
        }
    }

    dfs('', 0, 0);

    return answer;
};

---

결론

part를 사용한 부분이 문제를 좀 더 쉽게 해결할 수 있는 방법 중 하나라고 생각한다.

문제는 DFS로 접근해 해결