Bernard Wong
  • Software Engineer
  • Problems
    • Lowest Common Ancestor of a Binary Tree
    • Longest Substring Without Repeating Characters
    • Longest Palindromic Substring
    • Longest Common Prefix
    • Isomorphic Strings
    • Integer to Roman
    • Frog Jump
    • Find the Difference
    • Find k closest elements to a given value
    • Longest Common Subsequence
    • Binary Search Tree from Sorted Array
    • Balanced Binary Tree
    • Sort Using Two Stacks
    • O(1) Stack
    • k-th element to last of a LinkedList
    • Dedup LinkedList
    • Check Rotated String
    • Compress String by Character Count
    • Escape HTML whitespace
    • Check String Permutation
    • Unique String
    • Container With Most Water
    • 4 Sum
    • 3 Sum Closest
    • 3 Sum
    • 2 Sum
    • Maximum Subarray
    • Nested List Weight Sum
    • Palindrome Number
    • Pow(x, n)
    • Regular Expression Matching
    • Remove Nth Node From End of List
    • Reverse Integer
    • Roman to Integer
    • Rotate Array
    • Search a 2D Matrix
    • Shortest Word Distance
    • Two Sum III - Data structure design
    • Valid Parentheses
    • ZigZag Conversion
    • Quicksort
    • Add Two Numbers
    • Best Time to Buy and Sell Stock
    • Letter Combinations of a Phone Number
  • Data Structures
    • Heap
Powered by GitBook
On this page
  1. Problems

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:

Digit string "23"

Output:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

val counts = Vector(3, 3, 3, 3, 3, 4, 3, 4)

// generate char mapping for given int char
def decode(c: Char): Seq[Char] = {
  val index = c.toInt - '2'.toInt
  for (i <- 0 until counts(index)) yield (counts.take(index).sum + 'a'.toInt + i).toChar
}

// complete keypad mappings
val mappings: Map[Char, Seq[Char]] = {
  (for (i <- '2' to '9') yield (i -> decode(i))).toMap
} withDefaultValue Seq(' ')

/**
  * generate each combination starting from last index.
  *
  * @param digits
  * @return
  */
def letterCombinations(digits: String): List[String] = {
  var ret: List[String] = Nil
  if (digits.isEmpty) ret
  else {
    val letters: Array[Char] = Array.fill(digits.length) {
      ' '
    }
    def generate(index: Int): Unit = {
      for (c <- mappings(digits(index))) {
        letters(index) = c
        if (index == 0) {
          ret = letters.mkString("") :: ret
        } else {
          generate(index - 1)
        }
      }
    }
    generate(digits.length - 1)
    ret
  }
}

/**
  * generate each combination but fixed length
  *
  * @param digits
  * @return
  */
def letterCombinations(digits: Array[Char]): Seq[String] = {
  if (digits.length != 7) throw new Error("must be 7 digits")
  else {
    for {
      a <- mappings(digits(0))
      b <- mappings(digits(1))
      c <- mappings(digits(2))
      d <- mappings(digits(3))
      e <- mappings(digits(4))
      f <- mappings(digits(5))
      g <- mappings(digits(6))
    } yield (s"$a$b$c$d$e$f$g")
  }
}

letterCombinations("2463832")
letterCombinations("2463832".toCharArray)

PreviousBest Time to Buy and Sell StockNextData Structures

Last updated 6 years ago