# 03.08.2023 [17. Letter Combinations of a Phone Number]

Possible words from phone keyboard

03.08.2023

17. Letter Combinations of a Phone Number medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/297

Problem TLDR

Possible words from phone keyboard

Intuition

Just a naive DFS and Backtraking will solve the problem, as the number is short

Approach

• pay attention to keys in keyboard, some have size of 4

Complexity

• Time complexity:
  O(n4^n), recursion depth is n, each time we iterate over ‘3’ or ‘4’ letters, for example:

12 ->
abc def
a   d
a    e
a     f
 b  d
 b   e
 b    f
  c d
  c  e
  c   f

Each new number multiply the previous count by 3 or 4. The final joinToString gives another n multiplier.

• Space complexity:
  O(4^n)

Code

    fun letterCombinations(digits: String): List<String> = mutableListOf<String>().apply {
      val abc = arrayOf("abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
      val list = Stack<Char>()
      fun dfs(pos: Int) {
        if (list.size == digits.length) {
          if (list.isNotEmpty()) add(list.joinToString("")) 
        } else abc[digits[pos].toInt() - '2'.toInt()].forEach { 
          list.push(it)
          dfs(pos + 1)
          list.pop()
        }
      }
      dfs(0)
    }