Daily LeetCode Challenge - 131. Palindrome Partitioning

Problem From.

https://leetcode.com/problems/palindrome-partitioning/

오늘 문제는 주어진 String s 에서 각각의 subString 이 palindrome 이 되는 경우를 반환하는 문제였다.

오늘 문제도 역시 DFS 와 백트래킹을 사용하여 풀 수 있었다.

index 를 기준점으로 가져가면서 i 부터 일정 범위가 palindroem 인지 확인하며 DFS 에 넣어주면 되었다.

class Solution {
    
    val answer = arrayListOf<List<String>>()
    
    fun partition(s: String): List<List<String>> {
        
        val temp = arrayListOf<String>()
        DFS(s, 0, temp)
        
        return answer
    }
    
    private fun DFS(s: String, index: Int, list : ArrayList<String>) {
        
        if(index >= s.length) {
            answer.add(list.toList())
            return
        }
        
        for(i in index until s.length) {
            
            val part = s.slice(index..i)
            
            if(!isPalindrome(part)) continue
            
            list.add(part)
            DFS(s, i + 1, list)
            list.removeAt(list.size - 1)
            
        }
        
    }
    
    private fun isPalindrome(part: String) : Boolean {
        var left = 0
        var right = part.length - 1
        while(left < right) {
            if(part[left] != part[right]) return false
            left += 1
            right -= 1
        }
        return true
    }
    
}