[LeetCode] Letter Combinations of a Phone Number (Java)

Given a digit string, 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.

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

1
2

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

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Analysis

It’s a easy question. But we can do it both in recursive way and iterative way.

In the iterative way, we use the result from the previous digits, and then add new letters to them.

Code

Recursive version

public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> rec = new LinkedList<>();
        StringBuilder string = new StringBuilder();
        letterCombinations(digits, 0, letters, string, rec);
        return rec;
    }
    
    private void letterCombinations(String digits, int number, String[] letters, StringBuilder string, List<String> rec) {
        if (digits.length() == number) {
            rec.add(string.toString());
            return;
        }
        String letter = letters[digits.charAt(number) - '2'];
        for (int i = 0; i < letter.length(); i++) {
            string.append(letter.charAt(i));
            letterCombinations(digits, number + 1, letters, string, rec);
            string.deleteCharAt(string.length() - 1);
        }
    }
}

public class Solution {

public List<String> letterCombinations(String digits) {

String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

List<String> rec = new LinkedList<>();

StringBuilder string = new StringBuilder();

letterCombinations(digits, 0, letters, string, rec);

return rec;

}

private void letterCombinations(String digits, int number, String[] letters, StringBuilder string, List<String> rec) {

if (digits.length() == number) {

rec.add(string.toString());

return;

}

String letter = letters[digits.charAt(number) - '2'];

for (int i = 0; i < letter.length(); i++) {

string.append(letter.charAt(i));

letterCombinations(digits, number + 1, letters, string, rec);

string.deleteCharAt(string.length() - 1);

}

Iterative version

public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        LinkedList<String> list = new LinkedList<>();
        list.add("");
        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '2';
            int size = list.size();
            for (int k = 0; k < size; k++) {
                String tmp = list.pop();
                for (int j = 0; j < letters[num].length(); j++)
                    list.add(tmp + letters[num].charAt(j));
            }
        }
        List<String> rec = new LinkedList<>();
        rec.addAll(list);
        return rec;
    }
}

public class Solution {

public List<String> letterCombinations(String digits) {

String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

LinkedList<String> list = new LinkedList<>();

list.add("");

for (int i = 0; i < digits.length(); i++) {

int num = digits.charAt(i) - '2';

int size = list.size();

for (int k = 0; k < size; k++) {

String tmp = list.pop();

for (int j = 0; j < letters[num].length(); j++)

list.add(tmp + letters[num].charAt(j));

}

List<String> rec = new LinkedList<>();

rec.addAll(list);

return rec;

}

Complexity

Assuming the average number of letters on every number is m, and the length of digits string is n, then the complexity is O(mⁿ).