[LeetCode][17. Letter Combinations of a Phone Number] 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explanation

发表于 2022-05-09 更新于 2024-03-05 分类于 Leetcode Waline：阅读次数：本文字数： 5.3k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explanation of Problem 17. Letter Combinations of a Phone Number.

Here shows 4 Approaches to slove this problem: Brute Force, Backtracking, BFS and Queue.

Intuition

Take the \(234\) for example, look at the tree:

Brute Froce(4 Loops)

Since the \(\textit{digits.length} <= 4\), we can just use the brute force approach \(4\) Loops to search all the possible combinations.

The total states is \(A(n,n)=A(4,4)=4!\). We have to enumerate all these states to get the answer.

public static List<String> letterCombinations_4Loops(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return ans;
    }

    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int len = digits.length();
    int[] digitsArr = new int[len];
    for (int i = 0; i < len; i++) {
        digitsArr[i] = digits.charAt(i) - '0';
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append("a");
    }

    for (int i = 0; i < letters[digitsArr[0] - 2].length(); i++) {
        sb.replace(0, 1, letters[digitsArr[0] - 2].charAt(i) + "");
        if (len == 1) {
            ans.add(sb.substring(0, 1));
        }

        for (int j = 0; len >= 2 && j < letters[digitsArr[1] - 2].length(); j++) {
            sb.replace(1, 2, letters[digitsArr[1] - 2].charAt(j) + "");
            if (len == 2) {
                ans.add(sb.toString());
            }

            for (int k = 0; len >= 3 && k < letters[digitsArr[2] - 2].length(); k++) {
                sb.replace(2, 3, letters[digitsArr[2] - 2].charAt(k) + "");
                if (len == 3) {
                    ans.add(sb.toString());
                }

                for (int l = 0; len >= 4 && l < letters[digitsArr[3] - 2].length(); l++) {
                    sb.replace(3, 4, letters[digitsArr[3] - 2].charAt(l) + "");
                    ans.add(sb.toString());
                }
            }
        }
    }

    return ans;
}

Analysis

Time Complexity: \(O(4^N)\)
Space Complexity: \(O(N)\)

Backtracking

For the first number, there are \(3\) options, and \(3\) options for the second number and so on.

The combinations from the first to the last will expand into a recursive tree.

When the index reaches the end of digits, we get a combination, and add it to the result, end the current recursion. Finally we will get all the combinations.

public static List<String> letterCombinations(String digits) {
    List<String> ans = new ArrayList<>();

    if (digits == null || digits.length() == 0) {
        return ans;
    }

    String[] lettersMap = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    backtrack(ans, new StringBuilder(), digits, lettersMap, 0);
    return ans;
}

public static void backtrack(List<String> res, StringBuilder sb, String digits, String[] lettersMap, int idx) {
    if (idx == digits.length()) {
        res.add(sb.toString());
        return;
    }

    int number = digits.charAt(idx) - '0';
    String numStr = lettersMap[number - 2];
    for (int i = 0; i < numStr.length(); i++) {
        sb.append(numStr.charAt(i));
        backtrack(res, sb, digits, lettersMap, idx + 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}

Analysis

Time Complexity: \(O(3^M \times 4^N)\)
Space Complexity: \(O(3^M \times 4^N)\)

BFS

At the beginning, it is an empty string.
The new layer is obtained by adding characters at the end of the previous layer.
After the new layer is obtained, the previous layer is not used.

public static List<String> letterCombinations_bfs(String digits) {
    List<String> res = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return res;
    }

    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    res.add("");
    for (char digit : digits.toCharArray()) {
        String curLetters = letters[digit - '2'];
        List<String> newRes = new ArrayList<>();

        for (String item : res) {
            for (char curDigit : curLetters.toCharArray()) {
                newRes.add(item + curDigit);
            }
        }

        res = newRes;
    }

    return res;
}

Analysis

Time Complexity: \(O(3^M \times 4^N)\)
Space Complexity: \(O(3^M \times 4^N)\)

Queue

Look at the gif, it’s easy to understand the queue solution.

First we enqueue each letter of the first number in the digits, and then combine the dequeued element with each letter of the second number and enqueue to the queue.

public static List<String> letterCombinations_queue(String digits) {
    if (digits == null || digits.length() == 0) {
        return new ArrayList<>();
    }

    int len = digits.length();
    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    Queue<String> queue = new LinkedList<>();
    int[] digitsArr = new int[len];
    for (int i = 0; i < len; i++) {
        digitsArr[i] = digits.charAt(i) - '0';
    }

    queue.offer("");
    for (int i = 0; i < len; i++) {
        String letter = letters[digitsArr[i] - 2];
        int size = queue.size();
        for (int j = 0; j < size; j++) {
            String temp = queue.poll();
            for (char ch : letter.toCharArray()) {
                queue.offer(temp + ch);
            }
        }
    }

    return new ArrayList<>(queue);
}

Analysis

Time Complexity: \(O(3^M \times 4^N)\)
Space Complexity: \(O(3^M \times 4^N)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗