Print All Possible Words from Phone Digits

Print all possible words from phone number digits.

This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem.

For example if input number is 234, possible words which can be formed are (Alphabetical order):
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4n would be the upper bound of number of words and not the minimum words.

private List<string> strs = new List<string>();
private int depth = 0;
char[] numbersArray;


 private char[] GetCharacters(char x)
{
    char[] arr;
    switch (x)
    {
        case '0': arr = new char[1] { '0' };
            return arr;
        case '1': arr = new char[1] { '1' };
            return arr;
        case '2': arr = new char[3] { 'a', 'b', 'c' };
            return arr;
        case '3': arr = new char[3] { 'd', 'e', 'f' };
            return arr;
        case '4': arr = new char[3] { 'g', 'h', 'i' };
            return arr;
        case '5': arr = new char[3] { 'j', 'k', 'l' };
            return arr;
        case '6': arr = new char[3] { 'm', 'n', 'o' };
            return arr;
        case '7': arr = new char[4] { 'p', 'q', 'r', 's' };
            return arr;
        case '8': arr = new char[3] { 't', 'u', 'v' };
            return arr;
        case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };
            return arr;
        default: return null; 
    }
}


private void PrintLetters(string numbers)
{

    this.numbersArray = numbers.ToCharArray();
    this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty);
}

private void PrintAllCombinations(char[] letters, string output)
{
    depth++;
    for (int i = 0; i < letters.Length; i++)
    {

        if (this.depth != 3)
        {
            output += letters[i];
            this.PrintAllCombinations(this.GetCharacters(
            	Convert.ToChar(this.numbersArray[depth])), output);
        }
        else
        {
            this.strs.Add(output + letters[i]);
        }
    }
}

5 Thoughts on “Print All Possible Words from Phone Digits

  1. please help me ,i can not understand that answers
    what is phone digit means

    • Anonymous on January 15, 2017 at 12:59 am said:

      “BABI”

      open your phone dial pad. and see the alphabets thats written on every number. the question is about how many possible words can be formed of the same respective buttons clicked on dial pad with the same length.

  2. Aditya Sharma on December 2, 2016 at 11:54 am said:

    an answer i solved .hope this could be way better
    public class PrintWords {
    public static Character[] getCharList(char x) {
    Character[] c ;
    if (x == ’0′) {
    c = new Character[] { ’0′};
    } else if (x == ’1′) {
    c = new Character[] { ’1′};
    } else if (x == ’2′) {
    c = new Character[] { ‘a’, ‘b’, ‘c’ };

    } else if (x == ’3′) {
    c =new Character[] { ‘d’, ‘e’, ‘f’ };
    } else if (x == ’4′) {
    c = new Character[] { ‘g’, ‘h’, ‘i’ };
    } else if (x == ’5′) {
    c = new Character[] { ‘j’, ‘k’, ‘l’ };
    } else if (x == ’6′) {
    c = new Character[] { ‘m’, ‘n’, ‘o’ };
    } else if (x == ’7′) {
    c = new Character[] { ‘p’, ‘q’, ‘r’, ‘s’ };
    } else if (x == ’8′) {
    c =new Character[] { ‘t’, ‘u’, ‘v’ };
    } else if (x == ’9′) {
    c =new Character[]{ ‘w’, ‘x’, ‘y’, ‘z’ };
    }else {
    return null;
    }

    return c;
    }
    public static List process(Character[] ch , List list1 ){
    int size =list1.size();
    List list2 =new ArrayList();
    for(int j =0;j<size;j++){
    for(int i=0;i<ch.length;i++){
    list2.add(list1.get(j)+""+ch[i]);
    }
    }
    list1 =list2;
    return list1;
    }
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    char c[] = s.toCharArray();
    List list = new ArrayList();
    list.add(" ");
    for (int i = 0; i < c.length; i++) {
    list = process(getCharList(c[i]), list);
    }
    System.out.println(list);
    }
    }

  3. saumya ranjan Mishra on January 9, 2017 at 8:11 pm said:

    the phone number digits is the old version of the keypad phone such as nokia225 while typing a msg it was written abc above 2 def in 3 and so on

  4. Suyog Choudhary on February 18, 2017 at 6:43 pm said:

    Excellent work man

Leave a Reply to Aditya Sharma Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation