Today I Learned

오늘도 코테!

Restore IP Addresses

Leetcode 93번 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.

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

풀이과정

• 주어진 숫자 문자열을 유효한 IPv4 주소로 변환해야된다. 백트래킹 알고리즘을 사용하여 가능한 모든 세그먼트 조합을 탐색하는 방법으로 문제를 풀었다.

1. 주어진 문자열을 가능한 모든 유효한 IPv4 주소로 분할해야 하는데, 문자열을 세그먼트로 분할하고 각 세그먼트의 유효성을 확인한다. 세그먼트의 길이는 1~3, 값은 0~255 사이여야 한다.

2. 백트래킹을 사용하여 가능한 모든 세그먼트 조합을 탐색한다. 재귀를 사용하여 각 단계에서 가능한 세그먼트를 선택하고, 다음 세그먼트를 탐색하기 위해 재귀 호출한다. 이 과정에서 유효하지 않은 세그먼트는 건너뛴다.

3. 세그먼트가 0으로 시작하지만 여러 자릿수인 경우 유효하지 않고, 세그먼트가 3자리인데 255보다 큰 경우 유효하지 않는다.

4. 모든 세그먼트가 선택되고 문자열을 모두 탐색한 경우, 현재까지 구성된 유효한 IPv4 주소를 결과 리스트에 추가한다. 주어진 문자열을 모두 처리했거나 세그먼트 수가 4를 초과한 경우, 탐색을 종료하고 결과를 반환한다.

Java 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(result, s, 0, "", 0);
        return result;
    }
    
    private void backtrack(List<String> result, String s, int index, String current, int count) {
        if (count > 4) return;
        if (count == 4 && index == s.length()) {
            result.add(current);
            return;
        }
        
        for (int i = 1; i < 4; i++) {
            if (index + i > s.length()) break;
            String segment = s.substring(index, index + i);
            if ((segment.startsWith("0") && segment.length() > 1) || (i == 3 && Integer.parseInt(segment) >= 256)) continue;
            backtrack(result, s, index + i, current + segment + (count == 3 ? "" : "."), count + 1);
        }
    }
}