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]);
        }
    }
}

One Thought on “Print All Possible Words from Phone Digits

  1. 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);
    }
    }

Leave a 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