[LeetCode#93] Restore IP Addresses

 

❐ Description

---

이번 문제는 기존의 순열이나 조합을 다루는 백트래킹 문제와는 달리, 입력이 문자열로 주어지고 이를

조각으로 나누어가며 탐색하는 백트래킹 유형이다. 문자열의 앞뒤를 탐색하며 유효성을 검증해야 하기

때문에, 문자열을 동적으로 분할하는 로직이 추가적으로 필요하다.

 

 

 

 

 

❐ 풀이 전략

---

☑️ 문자열 분할의 시작 지점을 cursor 변수에 저장한다.

☑️ IP의 8비트 최대 길이인 3만큼 for문을 순환한다.

☑️ 문자열 분할의 종료 지점을 cursor + length로 나타낸다.

☑️ 생성된 부분 문자열이 0으로 시작하지 않는 10의 자리 숫자 이상인지 확인한다.

☑️ 생성된 부분 문자열이 255 이하를 충족하는지 확인한다.

☑️ dot(점)의 수가 4개가 넘어간다면 해당 IP는 무시한다.

☑️ 현재 cursor가 input의 길이보다 크거나 같고, dot의 수가 4개라면 IP를 결과에 추가한다.

 

 

 

 

 

❐ Solution

---

public class Solution {

    List<String> answer = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backTracking(s, 0, 0, new StringBuilder());
        return answer;
    }

    public void backTracking(
        String input,
        int cursor,
        int dotCount,
        StringBuilder ip
    ){
        if (dotCount > 4) {
            return;
        }
        
        if (dotCount == 4 && cursor >= input.length()){
            answer.add(ip.substring(0, ip.length() - 1));
            return;
        }
        
        for (int length = 1; length <= input.length() && cursor + length <= s.length(); i++) {
            String segment = input.subString(cursor, cursor + length);
            if (segment.charAt(0) == '0' && segment.length() != 1) {
                break;
            }
            if (Integer.parseInt(segment) <= 255) {
                int prevLenght = ip.length():
                ip.append(segment).append(.);
                backTracking(input, cursor + length, dotcount + 1, ip);
                ip.setLength(prevLenght);
            }
        }
    }
}

 

 

 

 

 

 

---