Letter Combinations of a Phone Number Leetcode Solution
Letter Combinations of a Phone Number Leetcode Problem :
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"]
Letter Combinations of a Phone Number Leetcode Solution :
Constraints :
- 0 <= digits.length <= 4
- digits[i] is a digit in the range [‘2’, ‘9’].
Example 1:
Input: digits = “”
Output: []
Example 2:
Input: digits = “2”
Output: [“a”,”b”,”c”]
Idea :
The intuition behind this code is to use a recursive approach to generate all possible combinations. The function solve is the recursive function that does the job.
Approach:
- The function letter Combinations takes a string digits as input, representing a sequence of digits (e.g., “23” or “456”).
- It initializes an unordered map ‘mp’, which maps each digit to the corresponding letters on a phone keypad. For example, ‘2’ maps to “abc”, ‘3’ maps to “def”, and so on.
- A vector ans is declared to store the final result, i.e., all possible letter combinations.
- A string temp is used to store the temporary letter combination being constructed during each recursive call.
- The solve function is a recursive backtracking function. It takes an index idx, the ans vector, the digits string, the mp mapping, and the temp string.
- The base case of the recursion is when the idx reaches the end of the digits string. At this point, the temp string contains a valid letter combination, so it is added to the ans vector, and the function returns.
- If the base case is not met, the function processes the current digit at index idx. It retrieves the corresponding string of letters from the mp mapping and iterates through each letter.
- For each letter, it appends it to the temp string, and then makes a recursive call to solve with the next index (idx+1) to process the next digit in the digits string.
- After the recursive call returns, the last character is removed from the temp string using temp.pop_back(). This backtracking step is essential to explore all possible combinations correctly.
- The function letter Combinations initializes the temp string as an empty string and starts the recursion by calling solve(0, ans, digits, mp, temp).
- Finally, it returns the ans vector containing all the possible letter combinations.
Complexity:
Time complexity:
O(3^N)
Space complexity:
O(N^2 + 3^N)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
void f(int ind, string &digits, vector &v, string &s, map &m) {
if(ind == digits.size()) {
v.push_back(s);
return;
}
string t = m[digits[ind]];
for(int i = 0 ; i < t.size() ; i++) {
s+=t[i];
f(ind+1, digits, v, s, m);
s.pop_back();
}
}
vector letterCombinations(string digits) {
vector v;
if(digits.size() == 0) return v;
string s;
map m;
m['2'] = "abc";
m['3'] = "def";
m['4'] = "ghi";
m['5'] = "jkl";
m['6'] = "mno";
m['7'] = "pqrs";
m['8'] = "tuv";
m['9'] = "wxyz";
f(0, digits, v, s, m);
return v;
}
};
Java
class Solution {
public void solve(int idx, List ans, String digits, Map mp, StringBuilder temp) {
if (idx == digits.length()) {
ans.add(temp.toString());
return;
}
char ch = digits.charAt(idx);
String var1 = mp.get(ch);
for (int i = 0; i < var1.length(); i++) {
temp.append(var1.charAt(i));
solve(idx + 1, ans, digits, mp, temp);
temp.deleteCharAt(temp.length() - 1);
}
}
public List letterCombinations(String digits) {
if (digits.length() == 0)
return new ArrayList<>();
Map mp = new HashMap<>();
List ans = new ArrayList<>();
mp.put('2', "abc");
mp.put('3', "def");
mp.put('4', "ghi");
mp.put('5', "jkl");
mp.put('6', "mno");
mp.put('7', "pqrs");
mp.put('8', "tuv");
mp.put('9', "wxyz");
StringBuilder temp = new StringBuilder();
solve(0, ans, digits, mp, temp);
return ans;
}
}
Python
class Solution:
def solve(self, idx, ans, digits, mp, temp):
if idx == len(digits):
ans.append(''.join(temp))
return
ch = digits[idx]
var1 = mp[ch]
for char in var1:
temp.append(char)
self.solve(idx + 1, ans, digits, mp, temp)
temp.pop()
def letterCombinations(self, digits):
if len(digits) == 0:
return []
mp = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
ans = []
temp = []
self.solve(0, ans, digits, mp, temp)
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment