LeetCode-in-All

17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = “23”

Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

Example 2:

Input: digits = “”

Output: []

Example 3:

Input: digits = “2”

Output: [“a”,”b”,”c”]

Constraints:

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

Solution

import scala.collection.mutable.ListBuffer

object Solution {
    def letterCombinations(digits: String): List[String] = {
        if (digits.isEmpty) {
            return List.empty
        }

        val letters = Array("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
        val ans = ListBuffer[String]()

        def findCombinations(start: Int, nums: String, letters: Array[String], curr: StringBuilder): Unit = {
            if (curr.length == nums.length) {
                ans += curr.toString()
                return
            }
            for (i <- start until nums.length) {
                val n = nums(i).asDigit
                for (j <- 0 until letters(n).length) {
                    val ch = letters(n)(j)
                    curr.append(ch)
                    findCombinations(i + 1, nums, letters, curr)
                    curr.deleteCharAt(curr.length - 1)
                }
            }
        }

        findCombinations(0, digits, letters, new StringBuilder())
        ans.toList
    }
}

This site is open source. Improve this page.