LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 2 ~ 9의 숫자로 이루어진 문자열 digits
2. output: 숫자판에서 digits의 번호키를 눌러서 만들 수 있는 모든 문자열을 담은 배열 리턴

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Idea

미리 각 숫자별 입력 가능한 문자를 hashMap으로 저장한다.

결국 Combination 문제이므로 DFS로 해결 → Sol1

Solution

1. DFS

   • 미리 숫자 → 문자 hashMap을 초기화
   • 클릭할 숫자에 대해 DFS 탐색

   import java.util.*
   
   class Solution {
       // 각 키별 대응되는 문자
       val keyMap = hashMapOf<String, List<String>>("2" to listOf("a", "b", "c"),
           "3" to listOf("d", "e", "f"),
           "4" to listOf("g", "h", "i"),
           "5" to listOf("j", "k", "l"),
           "6" to listOf("m", "n", "o"),
           "7" to listOf("p", "q", "r", "s"),
           "8" to listOf("t", "u", "v"),
           "9" to listOf("w", "x", "y", "z")
       )
       val result = mutableListOf<String>()
       var input = ""
       fun letterCombinations(digits: String): List<String> {
           input = digits
           if (input == "") return listOf<String>()
           // dfs로 만들 수 있는 문자 탐색
           dfs("", 0)
           return result
       }
       // 만들 수 있는 문자 탐색
       fun dfs(s: String, len: Int) {
           if (len == input.length) { // 모든 버튼 다 클릭
               result.add(s)
               return
           }
           // 다음 버튼 클릭
           for (letter in keyMap.getOrDefault(input[len].toString(), listOf<String>())) {
               dfs(s + letter, len + 1)
           }
       }
   }
   

   시간 복잡도: 배열 순회(숫자 순회) X 배열 순회(문자 순회) = n^2

   

Point