leetcode: 17. Letter Combinations of a Phone Number

문제링크

풀이1

• DFS
  

class Solution {
    private fun getCombination(digits: String, buttons: List<String>, answer: MutableList<String>, output: String, index: Int) {
        if (digits.length == index) {
            answer.add(output)
            return
        }
        val digit = Character.getNumericValue(digits[index])
        for (letter in buttons[digit].toCharArray()) {
            getCombination(digits, buttons, answer, output + letter, index + 1)         
        }
    }
    fun letterCombinations(digits: String): List<String> {
        if (digits == "") return listOf()
        val answer = mutableListOf<String>()
        val buttons = listOf("0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")        
        getCombination(digits, buttons, answer, "", 0)        
        return answer
    }
}

풀이2

• BFS
  

class Solution {
    fun letterCombinations(digits: String): List<String> {
        if (digits == "") return listOf()
        val answer = mutableListOf<String>()
        val buttons = listOf("0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")        
        answer.add("")
        while (answer.first().length != digits.length) {
            val temp = answer.removeAt(0)
            val index = Character.getNumericValue(digits[temp.length])     
            for (letter in buttons[index].toCharArray()) {                
                answer.add(temp + letter)
            }
        }
        return answer
    }
}