Letter Combinations of a Phone Number Editorial

Practice Problem Link: Letter Combinations of a Phone Number

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string containing digits from 2 to 9 (inclusive), return all the possible letter combinations that the number could denote. The resultant list should be sorted lexicographically.

Approach

The approach is to store list of characters, matching with each of the numbers on the dial pad of the phone. Then for each digit in the given string, we try to match all the characters matching with it, with the previous digit in the given string, and generate all the possible strings in this way.

Analysis

• Time Complexity: O(Product of size of the set of characters matched with each digit of the string)
• Space Complexity: O(Product of size of the set of characters matched with each digit of the string)

Implementation

C++

vector<vector<char>> charSet;
vector<string> result;
vector<char> characterList;
void solve(string digits,int idx,int n){
	if(idx == n){
		string auxiliary = "";
		for(char i: characterList){
			auxiliary += i;
		}
		if(auxiliary.length() == digits.length()) {
			result.push_back(auxiliary);
		}
		return;
	}
	for(int i = idx; i < n; i++){
		for(char ch: charSet[digits[i] - '0']){
			characterList.push_back(ch);
			solve(digits, i + 1, n);
			characterList.pop_back();
		}
	}
}
vector<string> letterCombinations(string digits) {
	result.clear();
	charSet.clear();
	int n = digits.length();
	for(int i = 0; i <= 9; i++) {
		vector<char> temp;
		charSet.push_back(temp);
	}
	char ch = 'a';
	for(int i = 2; i <= 9; i++) {
		if(i != 7 && i != 9)
		for(int j = 0; j < 3; j++) {
			charSet[i].push_back(ch);
			ch++;
		}
		else{
			for(int j = 0;j < 4; j++){
				charSet[i].push_back(ch);
				ch++;
			}		
		}
	}
	solve(digits, 0, n);
	return result;
}

Java

class Solution {
	ArrayList<ArrayList<Character>> charSet;
	List<String> result;
	ArrayList<Character> characterList = new ArrayList<>();
	void solve(String digits,int idx,int n){
		if(idx == n){
			String auxiliary = "";
			for(char i: characterList){
				auxiliary += i;
			}
			if(auxiliary.length() == digits.length()) {
				result.add(auxiliary);
			}
			return;
		}
		for(int i = idx; i < n; i++){
			for(char ch: charSet.get(digits.charAt(i) - '0')){
				characterList.add(ch);
				solve(digits, i + 1, n);
				characterList.remove(characterList.size() - 1);
			}
		}
	}
	List<String> letterCombinations(String digits) {
		result = new ArrayList<>();
		charSet = new ArrayList<>();
		int n = digits.length();
		for(int i = 0; i <= 9; i++) {
			charSet.add(new ArrayList<>());
		}
		char ch = 'a';
		for(int i = 2; i <= 9; i++) {
			if(i != 7 && i != 9)
			for(int j = 0; j < 3; j++) {
				charSet.get(i).add(ch);
				ch++;
			}
			else{
				for(int j = 0;j < 4; j++){
					charSet.get(i).add(ch);
					ch++;
				}		
			}
		}
		solve(digits, 0, n);
		return result;
	}
}