We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:
Problem Statment
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 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Approach 1: DFS
- Time: O(n4^n)O(n4n)
- Space: O(4^n)O(4n)
Letter Combination Of Phone Number Program Solution In C++
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
vector<string> ans;
dfs(digits, 0, "", ans);
return ans;
}
private:
const vector<string> digitToLetters{"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(const string& digits, int i, string&& path, vector<string>& ans) {
if (i == digits.length()) {
ans.push_back(path);
return;
}
for (const char letter : digitToLetters[digits[i] - '0']) {
path.push_back(letter);
dfs(digits, i + 1, move(path), ans);
path.pop_back();
}
}
};
Letter Combination Of Phone Number Program Solution In JAVA
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();
List<String> ans = new ArrayList<>();
dfs(digits, 0, new StringBuilder(), ans);
return ans;
}
private static final String[] digitToLetters = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
private void dfs(String digits, int i, StringBuilder sb, List<String> ans) {
if (i == digits.length()) {
ans.add(sb.toString());
return;
}
for (final char c : digitToLetters[digits.charAt(i) - '0'].toCharArray()) {
sb.append(c);
dfs(digits, i + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
Letter Combination Of Phone Number Program Solution In PYTHON
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digitToLetters = ['', '', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
ans = []
def dfs(i: int, path: List[chr]) -> None:
if i == len(digits):
ans.append(''.join(path))
return
for letter in digitToLetters[ord(digits[i]) - ord('0')]:
path.append(letter)
dfs(i + 1, path)
path.pop()
dfs(0, [])
return ans
Approach 2: Iterative
- Time: O(n4^n)O(n4n)
- Space: O(4^n)O(4n)
Letter Combination Of Phone Number Program Solution In C++ | 2nd Approach
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
vector<string> ans{""};
const vector<string> digitToLetters{"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
for (const char d : digits) {
vector<string> temp;
for (const string& s : ans)
for (const char c : digitToLetters[d - '0'])
temp.push_back(s + c);
ans = move(temp);
}
return ans;
}
};
Letter Combination Of Phone Number Program Solution In JAVA | 2nd Approach
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();
List<String> ans = new ArrayList<>();
ans.add("");
final String[] digitToLetters = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
for (final char d : digits.toCharArray()) {
List<String> temp = new ArrayList<>();
for (final String s : ans)
for (final char c : digitToLetters[d - '0'].toCharArray())
temp.add(s + c);
ans = temp;
}
return ans;
}
}
Letter Combination Of Phone Number Program Solution In PYTHON | 2nd Approach
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
ans = ['']
digitToLetters = ['', '', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
for d in digits:
temp = []
for s in ans:
for c in digitToLetters[ord(d) - ord('0')]:
temp.append(s + c)
ans = temp
return ans
