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)
Last updated