Leetcode Amazon Interview Questions

Letter Combinations of a Phone Number

Leetcode - No. 17

17 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Letter Combinations of a Phone Number

Problem Analysis

When we try to find the combination of something, we need to think about the dfs algorithm with the backtracking technique.

For each level, we consider only one digit and put one of its characters by order (using a for loop) and go the next digit. By using the StringBuilder we can append one character belongs to that specific digit and recording the digit by a digit counter.

While the digit counter meets the end which is equal to the length of the original digits, we add the current string collected by StringBuilder into the results.

After the current StringBuilder was added, we return the function and backtrack (which is remove the last character added in the current level) and either the for loop will help to fill in the next character belong to the same digit or the backtracking function will help to go to the next digit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
              def  - [ad]*
            / 
        [a] - def  - [ae]*
     /      \  
abc  -  [b]   def  - [af]*
 0   \         1           2 <- Add the StringBuilder into result
        [c] 
```    


### Algorithm Analysis

BackTracking Algorithm + DFS Helper

In the dfsHelper: the base case is when indexOfDigit is equal the length of the original String which means we have already gone through whole digits. Add the current combination (temp result) into the result.

The feature of the combination is to record the index of currentString from the for the loop. Since each digit represented a signal string which has three, so we use a for loop to implement the backtracking algorithm. Add the specific character at i in the current String into the combination and put those variables into next DFS (with indexOfDigit + 1) which mean to pass the next digit in the original string. After passing the dfsHelper when we meet the base case and return to this level, remove the last character in the combination to the next i + 1 loop.

### Time Complexity Analysis

The time complexity of this should be 3^n, where n is the number of digits. For each digit you have 3 possible characters (excluding 7 and 9), and then for each subsequent digit, you get another 3 more possible characters per character of the previous digit.

O(3^N) if we use third for loop to solve
opt: O(N^2) : Backtracking

### Code Implementation - With PhoneNumber Class

```java
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        
        if(digits.length() == 0) {
            return results;
        }
        
        List<PhoneNumber> numberList = new ArrayList<>();

        for(char c : digits.toCharArray()) {
            numberList.add(new PhoneNumber(c));
        }
        backtracking(results, numberList, 0, new StringBuilder());
        return results;
    }
    
    public void backtracking(List<String> results, 
                             List<PhoneNumber> numberList, 
                             int indexOfPhoneNumber, 
                             StringBuilder combination) {
        
        /* When the indexOfPhoneNumber pass the last index */
        if(indexOfPhoneNumber == numberList.size()) {
            results.add(combination.toString());
            return;
        }
        
        /* Get the current String */
        String currentString = numberList.get(indexOfPhoneNumber).getString();
        
        /* Add the character one by one in each level (for each digit) */
        for(int i = 0; i < currentString.length(); i++) {
            combination.append(currentString.charAt(i));
            backtracking(results, numberList, indexOfPhoneNumber + 1, combination);
            combination.deleteCharAt(combination.length() - 1);
        }
    }
}

/* Can also use a function to deal with string retrieving */
class PhoneNumber {
    char number;
    public PhoneNumber(char num) {
        this.number = num;
    }
    
    public String getString() {
        switch (this.number) {
            case '2':
                return "abc";
            case '3':
                return "def";
            case '4':
                return "ghi";
            case '5':
                return "jkl";
            case '6':
                return "mno";
            case '7':
                return "pqrs";
            case '8':
                return "tuv";
            case '9':
                return "wxyz";
        }
        return "";
    }
}

Code Implementation - Without additional Class - No differences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() == 0) return result;
        StringBuilder combination = new StringBuilder();
        dfsHelper(digits, 0, result, combination);
        return result;
    }
    
    /* a -> ad -> a -> ae -> a -> af -> a -> b -> bd -> b -> bf -> .... -> c */
    public void dfsHelper(String digits, 
                          int indexOfDigits, 
                          List<String> result, 
                          StringBuilder combination) {

        if(indexOfDigits == digits.length()) {
            result.add(combination.toString());
            return;
        }
        
        /* get the current String by using the arugment of indexOfDigits to go through the next digit in the inpit */
        /* ex. 2 for  "abc" -> 3 for "def"  */
        String currentString = getString(digits.charAt(indexOfDigits));
        
            /* Get the first word and second word and third word in different level */
            /* Put the word into the StringBuilder and give it for the next handler */
            /* ex. "abc" chose "a" and put it in the dfs helper with index + 1, later, in "def" chose 'd' for next character*/
            /* a -> b -> c  d -> e -> f */
        
        for(int i = 0; i < currentString.length(); i++) {
            combination.append(currentString.charAt(i));
            dfsHelper(digits, indexOfDigits + 1, result, combination);
            /* Backtracking - Remove the laste character in the StringBuilder */
            combination.deleteCharAt(combination.length() - 1);
        }
    }
    
    public String getString(char num) {
        switch (num) {
            case '2':
                return "abc";
            case '3':
                return "def";
            case '4':
                return "ghi";
            case '5':
                return "jkl";
            case '6':
                return "mno";
            case '7':
                return "pqrs";
            case '8':
                return "tuv";
            case '9':
                return "wxyz";
        }
        return "";
    }
}

FEATURED TAGS
Leetcode Amazon Interview Questions