Q22: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example :
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Solution:
class Solution {
private:
void letterCombinations(string digits, vector<string>& output, string &temp, vector<string>& pad, int index){
if(index == digits.size()){
output.push_back(temp);
return;
}
string value = pad[digits[index]-'0'];
for(int i=0; i<value.size(); i++){
temp.push_back(value[i]);
letterCombinations(digits, output, temp, pad, index+1);
temp.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
if(digits.empty()){
return {};
}
vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> output;
string temp;
letterCombinations(digits, output, temp, pad, 0);
return output;
}
};
Explantion:
>Private Function letterCombinations:
.This part is like a helper function inside our class.
.It takes a phone number as input, finds all possible letter combinations
based on the number, and stores them in a list.
.It uses a technique called "backtracking" to explore all options by trying
out different letters for each digit.
>Public Function letterCombinations:
.This is the main function that users can call.
.It checks if the input phone number is empty. If it is, it returns an
empty list.
.Otherwise, it sets up some initial stuff (like mapping of digits to letters)
and then calls the private function to do the real work.