Daily LeetCode Challenge - 93. Restore IP Addresses

Problem From.
https://leetcode.com/problems/restore-ip-addresses/

오늘 문제는 주어진 string s 를 잘라 ip 주소를 만들때, 주어진 조건에 맞게 만들 수 있는 ip 주소를 모두 리턴하는 문제였다.

오늘 문제도 DFS 와 backtracking 으로 풀 수 있는 문제였다.
앞에서부터 잘라서 1개 ~ 3개씩 넣으면서, 0으로만 이루어져 있거나 255 보다 큰 수가 나온다면 탐색을 멈추는 방법을 사용하여 문제의 조건에 맞는 ip 주소를 찾을 수 있었다.

class Solution {
    
    val answer = arrayListOf<String>()
    
    fun restoreIpAddresses(s: String): List<String> {
        
        if(s.length < 4 || s.length > 12) {
            return listOf<String>()
        }
        
        DFS(s, 0, "", 0)
        
        return answer.toList()
    }
    
    private fun DFS(s : String, index : Int, str : String, count : Int) {
        if(count > 4) return
        if(count == 4 && index == s.length) {
            answer.add(str)
            return
        }
        
        for(i in 1..3) {
            if(index + i > s.length) continue
            val part = s.slice(index until index+i)
            
            if ((part.startsWith("0") && part.length >1) || (part.toInt() > 255)) continue
            val dot = if(count == 3) "" else "."
            DFS(s, index + i, str + part + dot, count + 1)
        }
        
    }
    
}