[LeetCode] 93. Restore IP Addresses - 깊이우선탐색(DFS) + 구현(Implementation) JAVA

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

코드설명

깊이우선탐색(DFS) + 구현(Implementation)을 활용합니다.

 

문제에 주어진대로 구현하면됩니다.

유의할점은 '.' 가 추가 됨에 따라 마지막에 '.'의 개수 4개가 추가되고, 마지막 점은 제거해주어야 하므로 1을 제거한다는 점까지 유의합니다.

또한, '.' 은 반드시 총 4번 더해지므로 (3번같지만, 코드에서는 마지막 점을 제거하기에 로직상 4번) level은 총 4번이면서, start == s.length() 일때 정답에 추가해줍니다.

 

IP Address가 유효한지 체크하는 부분은,

길이가 2 이상이면서, 만약 첫번째 숫자가 '0'이라면 leadingZero인 것이므로 유효하지 않음을 알 수 있습니다.

또한, 숫자범위 0~255 의 경우 처음에 잘못하고 아래와 같이 잘못 코딩했습니다.

if(num < 0 && num > 255) return true;

OR (||) 조건이어야 하겠지요.

아래와 같습니다.

if(num < 0 || num > 255) return true;

 

구현에 실수가 없어야하는 문제입니다.

 

또한, String ret을 통해서 매번 힙 구간에 새로운 문자열 객체(String은 immutable이기에 값에 더해진다고 하면, 새로운 객체가 생성됨)가 계속 생성되므로 유의합니다. 이 문제에서는 문제없습니다.

 

더 최적화 하고 싶다면, StringBuilder를 활용하면 됩니다.

코드

정답코드1입니다.

class Solution {
    ArrayList<String> answer = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(0, 0, s, new String(""));
        return answer;
    }
    
    public void dfs(int level, int start, String s, String ret){
        if(level == 4 && start == s.length()){
            answer.add(ret.substring(0, s.length() + 4 - 1));
            return ;
        }
        
        if(start + 3 <= s.length()){
            String str1 = s.substring(start, start + 3);
            if(isLeadingZeroOrOutofBounds(str1) == false){
               dfs(level + 1, start + 3, s,  ret + str1 + ".");
            }
        }
        if(start + 2 <= s.length()) {
            String str2 = s.substring(start, start + 2);
            if(isLeadingZeroOrOutofBounds(str2) == false){
                dfs(level + 1, start + 2, s, ret + str2 + ".");
            }
        }

        if(start + 1 <= s.length()){
            String str3 = s.substring(start, start + 1);
            if(isLeadingZeroOrOutofBounds(str3) == false){
                dfs(level + 1, start + 1, s, ret + str3 + ".");
            }
        }
    }

    public boolean isLeadingZeroOrOutofBounds(String s){
        if( s.length() >= 2 && s.charAt(0) == '0') return true;
        int num = Integer.parseInt(s);
        if(num < 0 || num > 255) return true;
        return false;
    }

}