LeetCode 17. Letter Combinations of a Phone Number

LeetCode Problem No.17

No.16 is here

modalsoul.hatenablog.com

17. Letter Combinations of a Phone Number

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'].

Code

object Solution {
    val letters = List(
        List("a", "b", "c"),
        List("d", "e", "f"),
        List("g", "h", "i"),
        List("j", "k", "l"),
        List("m", "n", "o"),
        List("p", "q", "r", "s"),
        List("t", "u", "v"),
        List("w", "x", "y", "z")
    )
    def letterCombinations(digits: String): List[String] = {
        if(digits.isEmpty) return List.empty[String]
        digits.map(_.asDigit).map(x => letters(x-2)).foldLeft(List(""))(
            (z, n) =>
                if(z.isEmpty) n
                else z.flatMap{ x => n.map(y => x + y)}
        )
    }
}

Methods

• Define letters as list.
• Convert digits to number list and convert to list of letters item.
• (((N1 x N2) x N3)... x Nn)
  • use foldLeft
• String => List[Int] => List[List[String]] => List[String]

Results

Runtime: 476 ms, faster than 96.70% of Scala online submissions for Letter Combinations of a Phone Number.

Memory Usage: 52.8 MB, less than 94.51% of Scala online submissions for Letter Combinations of a Phone Number.

⛳

Use reduceLeft

def letterCombinations(digits: String): List[String] = {
  if(digits.isEmpty) return List.empty[String]
  digits.map(_.asDigit).map(d => chars(d-2)).reduceLeft(
    (z, n) => z.flatMap{ x => n.map(y => x + y)}
  )
}