문제

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

문제 해석

2 ~ 9까지 주어진 숫자에는 각각 알파벳을 형상화 한다.
예를 들어 2 -> a,b,c를 표현할 수 있다. 뭐 이런식으로 말이다.
이랬을 떄 숫자가 주어지면 만들 수 있는 문자열을 전부 나열하라는 문제다.

문제 해결

필요한 거
1. 각 숫자마다 매칭해 넣을 문자열 map
2. 완전 탐색 기술

코드

class Solution {
    val map = mapOf<Char,String>(
        '2' to "abc",
        '3' to "def",
        '4' to "ghi",
        '5' to "jkl",
        '6' to "mno",
        '7' to "pqrs",
        '8' to "tuv",
        '9' to "wxyz"
    )
    
    fun letterCombinations(digits: String): List<String> {
        val res = mutableListOf<String>()
        if (digits.isEmpty()) {
            return res
        }
        combination(res,digits,"",0)
        return res
    }
    
    fun combination(res: MutableList<String>,digits: String, temp: String, level: Int) {
        if (level == digits.length) {
            res.add(temp)
            return
        }
        val c = map.get(digits.get(level))
        c?.toCharArray()?.forEach {
            combination(res,digits,temp + it.toString(),level + 1)
        }
    }
}

핵심은 combination 함수인거 같다.

먼저 함수가 digits 문자열을 끝까지 탐색했는지를 알려 줄 수 있는 level 변수를 하나 둔다.
이후 재귀의 종결 조건을 level == digits.length로 하고, 종결되었을 경우, 만들어진 문자열 temp를 리스트에 넣고 종료한다.

재귀의 종결 조건을 만들었다면 재귀해야할 로직을 넣어줘야 하는데, 먼저 digits의 각 문자가 표현할 수 있는 문자들을 map에서 찾아내고, 각각 이 변수들을 반복해서 temp에 넣어주고 재귀를 반복하면 결국엔 temp변수에 가능한 문자열들이 생겨나게 될 것이다.

상태공간트리를 만들어서 문제를 푼다면 더욱 쉽게 이해할 수 있다.