Once upon a time I was presented with the following test in an interview:
Given a mapping of digits to an array of characters, ie.
"1"={},
"2"={"A","B","C"},
"3"={"D","E","F"},
etc.
Print out all the string permutations a given input of digits maps to.
So for instance the string “23” should return:
AD
AE
AF
BD
BE
BF
CD
CE
CF
Another way to think of this is a function that returns all the possible combinations of letters the digits could represent if they were keypresses on a standard phone keypad.
I did a pretty bad job at this when I was asked it, partly because it was quite late at night, and partly because it’s not the sort of thing you find yourself doing that often, but today I found myself with a little bit of spare time on my hands and thought I’d give it another go.
I chose to do it in Scala rather than in Java which I had used last time and of course this led to the solution being much more elegant and succinct. If fact this is exactly the sort of problem that demonstrates the value of functional programming.
import collection.immutable.{List, Map}
import java.lang.String
object PhoneNumbers extends App {
val input = "1234"
val data = Map(
0 -> List("0"),
1 -> List("1"),
2 -> List("a", "b", "c"),
3 -> List("d", "e", "f"),
4 -> List("g", "h", "i"),
5 -> List("j", "k", "l"),
6 -> List("m", "n", "o"),
7 -> List("p", "q", "r", "s"),
8 -> List("t", "u", "v"),
9 -> List("w", "x", "y", "z")
)
getCombinations(input.substring(0, 1), input.substring(1))
.foreach(f => Console.println(f))
def getCombinations(current: String, remaining: String): List[String] = {
val vals = data(Integer.parseInt(current));
if (remaining.length() == 0)
return vals
val restOfString = getCombinations(remaining.substring(0, 1), remaining.substring(1))
vals
.map(f => restOfString.map(f2 => f + f2))
.flatten
}
}
