Letter Combinations of a Phone Number
Given a string S containing digits from 2 to 9 inclusive. Your task is to find all possible letter combinations that the number could represent.

A mapping from Digits to Letters (just like in Nokia 1100) is shown below. Note that 1 does not map to any letter.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then the 'T' test cases follow. The first and only line of each test case contains string S.

Output Format

For each test case, the list containing all the combinations of letters will be printed. The output of each test case is printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function. The output strings can be returned in any order.

Constraints:

1

Question

Letter Combinations of a Phone Number

Given a string S containing digits from 2 to 9 inclusive. Your task is to find all possible letter combinations that the number could represent.

A mapping from Digits to Letters (just like in Nokia 1100) is shown below. Note that 1 does not map to any letter.

example

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the 'T' test cases follow.

The first and only line of each test case contains string S.

Output Format

For each test case, the list containing all the combinations of letters will be printed.

The output of each test case is printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function.  

The output strings can be returned in any order.

Constraints:

1 <= T <= 10 
1 <= |S| <= 10 
2 <= S[i] <=9  

Where |S| is the length of string 'S" and 'S[i]' represents the element of the string S. 

Time Limit: 1 sec

Accepted Answer

Recursion, Backtracking, with memorization java

Accepted Answer

Backtracking approach

The idea is to find all possible combinations of letters using backtracking.
Backtracking is an algorithm to find all possible solutions by exploring all potential candidates. If the current solution does not turn out to be a solution or is not possibly the last solution, this algorithm backtracks and makes some changes on the previous steps.

Algorithm:

Let’s say we have a backtrack function, combinationsHelper(combination, nextDigits) which takes the ongoing letter combination and next digits (which we need to map to letters) as its arguments.
Base Case: If there are no more digits to check, that means that the current combination is done.
If there are still digits to check :

a. Iterate over the letters mapping the next available digit.

b. Append the current letter to the current combination and proceed to check the next digits.

Space Complexity: OtherExplanation:

O(3^N * 4^M), where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

Since we are storing all the possible combinations, thus the final space complexity is O(3^N * 4^M).

Time Complexity: OtherExplanation:

O(3^N * 4^M), where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

Numbers {2, 3, 4, 5, 6, 8} map to 3 letters and numbers {7, 9} map to 4 letters. Generating combinations of a string of length L takes K^L time, where K is the number of letters that each digit maps to. Thus, the final time complexity will be O(3^N * 4^M).

Java (SE 1.8)

/*

	Time Complexity: O(3^N * 4^M) 

	Space Complexity: O(3^N * 4^M)

	

	where 'N' is the number of digits in the string 'S' that maps to 3 letters and 'M' is the number of digits in the string 'S' that maps to 4 letters

*/



import java.util.ArrayList;



public class Solution 

{

    public static void combinationsHelper(String digits, String[] digToStr, int j, String temp, ArrayList ans)

    {

        

        // If we have reached the end of input string, push current string in ans

        if(j == digits.length()){

    

            ans.add(temp);

            return;

        }

        

        // Converting char to int

        int val = digits.charAt(j) - '0';

        

        // For all the characters corresponding to current digit, find all possible combinations

        for(int i = 0 ; i < digToStr[val].length() ; i++)

        {

            

            temp += digToStr[val].charAt(i);

            combinationsHelper(digits,digToStr,j+1,temp,ans);

            

            // Backtracking step, popping the previous consideration for current digit to find combinations corresponding to other characters of the current digit

             temp = temp.substring(0, temp.length() - 1);

        }

    }



    public static ArrayList combinations(String s)

    {

	

		// Mapping of all the digits to their respective char string

	    String[] digToStr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

	

	    // Size of input string

        int n =  s.length();

    

        // Temporary string

        String temp = new String();

    

        // For storing all the possible combinations

        ArrayList ans = new ArrayList<>();

    

        // If the input string is empty return ans

        if(n == 0)

        {

    	   return ans;

        }

        

        // Backtracking function

        combinationsHelper(s,digToStr,0,temp,ans);

    

        return ans;	

	}

}

Python (3.5)

'''



	Time complexity: O(3^N * 4^M) 

	Space complexity: O(3^N * 4^M)

	

	where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

'''





def combinationsHelper(digits, digToStr, j, temp, ans):



    # If we have reached the end of input string, push current string in ans

    if(j == len(digits)):

        ans.append(temp)

        return



    # Converting char to int

    val = ord(digits[j]) - ord('0')



    # For all the characters corresponding to current digit, find all possible combinations

    for i in range(len(digToStr[val])):



        temp += digToStr[val][i]

        combinationsHelper(digits, digToStr, j + 1, temp, ans)



        # Backtracking step, popping the previous consideration for current digit to find combinations corresponding to other characters of the current digit

        temp = temp[:-1]





def combinations(s):



    # Mapping of all the digits to their respective char string

    digToStr = ["", "", "abc", "def", "ghi",

                    "jkl", "mno", "pqrs", "tuv", "wxyz"]



    # Size of input string

    n = len(s)



    # Temporary string

    temp = ""



    # For storing all the possible combinations

    ans = []



    # If the input string is empty return ans

    if(n == 0):

        return ans



    # Backtracking function

    combinationsHelper(s, digToStr, 0, temp, ans)



    return ans

C++ (g++ 5.4)

/*



	Time complexity: O(3^N * 4^M) 

	Space complexity: O(3^N * 4^M)

	

	where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

 



*/



void combinationsHelper(string digits, string digToStr[], int j, string temp, vector&ans){

        

    // If we have reached the end of input string, push current string in ans

    if(j == digits.length()){



        ans.push_back(temp);

        return;

    }

    

    // Converting char to int

    int val = digits[j]-'0';

    

    // For all the characters corresponding to current digit, find all possible combinations

    for(int i=0;i    	

        temp.push_back(digToStr[val][i]);

        combinationsHelper(digits,digToStr,j+1,temp,ans);

        // Backtracking step, popping the previous consideration for current digit to find combinations corresponding to other characters of the current digit

        temp.pop_back();   

    }

}

    

vector combinations(string s){

	

	// Mapping of all the digits to their respective char string

	string digToStr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

	

	// Size of input string

    int n =  s.length();

    

    // Temporary string

    string temp;

    

    // For storing all the possible combinations

    vectorans;

    

    // If the input string is empty return ans

    if(n == 0){

    	return ans;

    }

    // Backtracking function

    combinationsHelper(s,digToStr,0,temp,ans);

    

    return ans;

}

Given a string S containing digits from 2 to 9 inclusive. Your task is to find all possible letter combinations that the number could represent.

Input format:

Output Format

Note

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer