Suppose Your Are Writing a Message to Your Friends , Assume Simple Mobile of Old Time Where You Don't Had Seperate buttons for chars , so you have to type some digit and that show you number of possible chars , now suppose you press some random keys on mobile & send some fake message to your friendsCan You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed.

e.g. if numbers pressed 9876124305 then output should be same as in this file https://ideone.com/VtoBo

Can You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed. What Will Be Time and Space Complexity .

Follow Up:

Can You Output only those strings that are in a given dictionary. (and length of the dictionary is small.) What Will Be Complexity of Problem , Explain Clearly .

Algorithm:

Data Structure used : Array

Problem Solving Paradigm Used: Recursion

class Number2Text
{       // Mapping From 0-9 Number in to Corresponding Strings  
        // when you press 1 only 1 is showed , when you press 0 , 0 is showed 
        //those assume simple mobile else 1 used to show many chars then we can store 
       //chars in string and can pass thi string at 1st string in below array.
       //e.g. lest 1 may support 1 -> , . ! ~ @ # $ % ^ & * ( ) { } [ ] / ? : ; " ' etc.
       //so we can write String one=" ,.!~@#$%^&*(){}[]/?:;"' "; can pass one string 
       //to below 
         
         private static String[] mapping = {"0","1","ABC", "DEF", "GHI", "JKL", "MNO",
                        "PQRS", "TUV", "WXYZ"};
 
 
public static void combinations(int[] number, char[] buf, int numIndex) 
{
 
          for (int i = 0; i < mapping[number[numIndex]].length(); i++) 
         {
                        buf[numIndex] = mapping[number[numIndex]].charAt(i);
                        if (numIndex < number.length - 1) 
                        {
                                combinations(number, buf, numIndex + 1);
                        } 
                        else
                                System.out.println(buf);
         }
}
 
 
 
public static void main(String[] args)  
{
                int num[] ={9,8,7,6,1,2,4,3,0,5};// { 5, 8, 5, 5, 0, 3, 3, 4, 4, 7 };
                Number2Text.combinations(num, new char[num.length], 0); 
} 
 
}

Time Complexity O(4*T(n-1)) //Worst Case

Space Complexity O(N)

Run Here Small Input https://ideone.com/9T6yb

              Average Size Input https://ideone.com/T07Qy

              Large Input https://ideone.com/l4sbz

Aplplication : Frequently Used in Mobile Phone  , When You Type Message , it Show you Different Combinations. Its Great Code :) .

Feel Free to Comment on anything you like such that how we can improve complexity , other way to solve same problem or if anything wrong here , Thanks for visiting.