[Java] leetcode 93. Restore IP Addresses

문제

Restore IP Addresses - LeetCode

Restore IP Addresses - LeetCode

필요한 개념

자바

• 재귀 함수
• 링크드 리스트
• 문자열을 숫자로 파싱 Integer.parseInt()
• 문자열의 substring 메소드

풀이

재귀 함수 helper을 만들어서 레벨 탐색 풀이하였다. 재귀 함수의 로직은 다음과 같다. 

1. 각 재귀 함수마다 1..3 반복문을 돈다. 
2. 01,02,03.. 0으로 시작하는 숫자들, 255 이상인 숫자들 을 제외한다.
3. 레벨을 올려 가며 다음 재귀로 넘어간다. 
4. 종료 조건일 때 현재 시작 인덱스 idx 가 주어진 Original_string.length() 일때만 정답 리스트에 추가한다.
5. 정답 리스트를 리턴한다. 

참고

재귀가 익숙하지 않은 분들은 참고하세요

각 레벨에서 할수 있는 행동은 다음과 같다. 

• 1개 숫자를 추가
• 2개 숫자를 추가
• 3개 숫자를 추가

각 숫자가 문제에서 주어진 조건에 맞으면 다음 재귀로 넘어간다. 

코드

 

자바

class Solution {
    List<String> ans;
    String temp_str;
    public List<String> restoreIpAddresses(String s) {
        ans = new ArrayList<>();
        if(s.length() > 12)return ans;        

        helper(s, "", 0, 0);
        return ans;
    }
    public void helper(String s, String cur_str,int level,int idx){
        if(level == 4){
            if(idx == s.length())
                ans.add(cur_str.substring(0, cur_str.length()-1));
            return;
        }
        for(int i =1 ;i < 4; i++){
            if(i + idx-1 < s.length()) temp_str = s.substring(idx,idx+ i );
            if(( i > 1 && temp_str.charAt(0) == '0' ) || getN(temp_str) > 255 )continue;
            helper(s,cur_str + temp_str + "." , level + 1, idx + i);
        }
        
    }
    public int getN(String x){
        return Integer.parseInt(x);
    }
}