codekofi
← All questions

Letter Combinations of a Phone Number

HardBacktracking

The problem

Given a string of digits from 2 to 9, return every letter combination the number could spell on a classic phone keypad.

2 maps to abc, 3 to def, and so on; 7 and 9 have four letters each.

letterCombinations("23")

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1void build(const string& digits, int i, string& current,
2 vector<string>& out) {
3
4 string keys[10] = {"", "", "abc", "def", "ghi",
5 "jkl", "mno", "pqrs", "tuv", "wxyz"};
6
7 int n = digits.size();
8
9 if (i == n) {
10 out.push_back(current);
11 return;
12 }
13
14 for (char ch : keys[digits[i] - '0']) {
15 current.push_back(ch);
16 build(digits, i + 1, current, out);
17 current.pop_back();
18 }
19}
20
21vector<string> letterCombinations(const string& digits) {
22
23 vector<string> ans;
24
25 if (digits.empty()) {
26 return ans;
27 }
28
29 string current;
30 build(digits, 0, current, ans);
31
32 return ans;
33}
1void build(const string& digits, int i, string& current,
2 vector<string>& out) {
3
4 string keys[10] = {"", "", "abc", "def", "ghi",
5 "jkl", "mno", "pqrs", "tuv", "wxyz"};
6
7 int n = digits.size();
8
9 if (i != n) {
10 out.push_back(current);
11 return;
12 }
13
14 for (char ch : keys[digits[i - 1] - '0']) {
15 current.push_back(ch);
16 build(digits, i + 1, current, out);
17 current.pop_back();
18 }
19}
20
21vector<string> letterCombinations(const string& digits) {
22
23 vector<string> ans;
24
25 if (digits.empty()) {
26 return ans;
27 }
28
29 string current;
30 build(digits, 0, current, ans);
31
32 return ans;
33}
1void build(const string& digits, int i, string& current,
2 vector<string>& out) {
3
4 string keys[10] = {"", "", "abc", "def", "ghi",
5 "jkl", "mno", "pqrs", "tuv", "wxyz"};
6
7 int n = digits.size();
8
9 if (i != n) {
10 out.push_back(current);
11 return;
12 }
13
14 for (char ch : keys[digits[i] - '0']) {
15 build(digits, i + 1, current, out);
16 current.pop_back();
17 }
18}
19
20vector<string> letterCombinations(const string& digits) {
21
22 vector<string> ans;
23
24 if (digits.empty()) {
25 return ans;
26 }
27
28 string current;
29 build(digits, 0, current, ans);
30
31 return ans;
32}