Possible Words From Phone Digits


Sun Feb 06 2022 23:42:45 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits

class Solution
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        return res;
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            //returning a list containing empty string.
            return baseRes; 
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
        String code = hash[ch - '0']; 
        for (String val : prevRes) { 
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
        //returning the list.
        return Res; 

Possible Words From Phone Digits Given a keypad as shown in the diagram, and an N digit number which is represented by array a[ ], the task is to list all words which are possible by pressing these numbers. Example 1: Input: N = 3, a[] = {2, 3, 4} Output: 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 Explanation: When we press 2,3,4 then adg, adh, adi, ... cfi are the list of possible words. Example 2: Input: N = 3, a[] = {3, 4, 5} Output: dgj dgk dgl dhj dhk dhl dij dik dil egj egk egl ehj ehk ehl eij eik eil fgj fgk fgl fhj fhk fhl fij fik fil Explanation: When we press 3,4,5 then dgj, dgk, dgl, ... fil are the list of possible words. Your Task: You don't need to read input or print anything. You just need to complete the function possibleWords() that takes an array a[ ] and N as input parameters and returns an array of all the possible words in lexicographical increasing order. Expected Time Complexity: O(4^N * N). Expected Auxiliary Space: O(N). Constraints: 1 ≤ N ≤ 10 2 ≤ a[i] ≤ 9 --------------------------------------------------------------------------------------------------------- Before the advent of QWERTY keyboards, texts and numbers were placed on the same key. For example, 2 has "ABC" if we wanted to write anything starting with 'A' we need to type key 2 once. If we wanted to type 'B', press key 2 twice and thrice for typing 'C'. Below is a picture of such a keypad. ______________________________ 1 ABC DEF 2 3 ______________________________ GHI JKL MNO 4 5 6 ______________________________ PQRS TUV WXYZ 7 8 9 ______________________________ * 0 # ______________________________ ---------------------------------------------------------------------------------------------------------