LeetCode_Restore IP Addresses (Java)

Leethub 으로 간단하게 Github에 문제와 코드를 업로드하세요!

93. Restore IP Addresses

Medium

---

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와 백트래킹으로 간단하게 풀 수 있다. 답을 만들 때는 Stringbuilder을 사용했다. 다시 백트래킹시킬때 setLength로 이전상황으로 만들었다.

코드

import java.util.*;

class Solution {
    static String str;
    static List<String> res;
    static StringBuilder sb;
    public List<String> restoreIpAddresses(String s) {
        str = s;
        res = new ArrayList<>();
        sb = new StringBuilder();

        int len = s.length();
        if(len <= 3 || len >= 13) return res;

        dfs(0, 0); // 0개, 0위치 -> 4개, 끝위치 까지 진행
        return res;
    }

    void dfs(int depth, int startIdx){
        if(depth == 4 && startIdx == str.length()){
            res.add(sb.toString());
            return;
        }

        if(depth > 4 || startIdx >= str.length()) return;

        for(int i=1; i<=3 && startIdx+i <= str.length(); i++){
            String part = str.substring(startIdx, startIdx + i);

            int prev_sbLen = sb.length();
            if(isValid(part)){
                if(prev_sbLen>0) sb.append(".");
                sb.append(part);
                dfs(depth+1, startIdx+i);
                sb.setLength(prev_sbLen);
            }
        }
    }

    boolean isValid(String s){
        int s_len = s.length();
        int num = Integer.parseInt(s);
        if(s_len == 1){
            return num >= 0 && num <= 9;
        }
        else if(s_len == 2){
            return num >= 10 && num <= 99;
        }
        else if(s_len == 3){
            return num >= 100 && num <= 255;
        }
        return false;
    }
}