NUHMAN.com

In this article, we will explore a common problem that you might have encountered while working with algorithms: generating all possible letter combinations from a string of digits on a traditional phone keypad.

For instance, the digit "2" on a phone keypad corresponds to the letters "abc", and "3" corresponds to "def". Given a string of digits, such as "23", our task is to return all possible letter combinations that the digits could represent.

We will break down the solution step by step, using an iterative approach and a Breadth-First Search (BFS) strategy.

🔍 The Problem: Phone Number Letter Combinations

On a traditional phone keypad, each number (from 2 to 9) corresponds to a set of letters. For example:

• 2 → "abc"
• 3 → "def"
• 4 → "ghi"
• And so on...

Given a string of digits, the goal is to return a list of all possible letter combinations that those digits could represent.

For example:

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

🧑‍💻 Java Solution

We’ll now look at the code for the Solution class, which implements the solution iteratively.

java

public class Solution {

    public static final String[] mapping = { "", "", "abc", "def", "ghi",
            "jkl", "mno", "pqrs", "tuv", "wxyz" };

    // Iterative, BFS version
    public List<String> letterCombinations(String digits) {
        List<String> cur = new ArrayList<String>();
        if (digits.length() == 0) {
            return cur;
        }
        cur.add("");
        for (int i = 0; i < digits.length(); i++) {
            String strs = mapping[digits.charAt(i) - '0'];
            List<String> next = new ArrayList<>();
            for (int j = 0; j < strs.length(); j++) {
                char ch = strs.charAt(j);
                // Try to insert 'ch' to each current combination
                for (String comb : cur) {
                    next.add(comb + ch);
                }
            }
            cur = next;
        }
        return cur;
    }
}

Let’s break this down:

🏗️ Class Structure

1. Mapping Array

java

public static final String[] mapping = { "", "", "abc", "def", "ghi", 
            "jkl", "mno", "pqrs", "tuv", "wxyz" };

This array is used to map each digit (from 2 to 9) to its corresponding set of letters. For example:

• mapping[2] corresponds to "abc"
• mapping[3] corresponds to "def"
• And so on.

The array also contains two empty strings at indices 0 and 1, since digits 0 and 1 don’t have any corresponding letters.

💡 The letterCombinations Method

This method generates all the possible letter combinations from the input string of digits. It uses a BFS approach to incrementally build the combinations.

2. Initializing the List

java

List<String> cur = new ArrayList<String>();

An empty list cur is initialized to store the combinations of letters.

3. Edge Case Handling

java

if (digits.length() == 0) {
    return cur;
}

If the input string is empty, the method returns the empty list cur.

4. Start with an Empty String

java

cur.add("");

An empty string is added to the list cur, marking the starting point for combinations.

5. Iterate Through the Digits

java

for (int i = 0; i < digits.length(); i++) {
    String strs = mapping[digits.charAt(i) - '0'];
    List<String> next = new ArrayList<>();

• The loop iterates through each digit in the input string digits.
• For each digit, the corresponding string of letters is retrieved from the mapping array. For example, for digit 2, it retrieves "abc".

6. Build New Combinations

java

for (int j = 0; j < strs.length(); j++) {
    char ch = strs.charAt(j);
    for (String comb : cur) {
        next.add(comb + ch);
    }
}

• For each character in the current mapping string (strs), a new combination is created by appending the character ch to each existing combination in cur.
• The new combinations are added to the next list.

7. Update the Current Combinations

java

cur = next;

Once all new combinations for the current digit are added to next, cur is updated to next. This allows the next iteration to work with the new set of combinations.

8. Return the Result

java

return cur;

After processing all the digits, cur will contain all possible letter combinations, which is returned as the final result.

📝 Summary of the Approach

This method uses an iterative, BFS-like approach to generate all possible letter combinations for the given digits:

1. Initialize: Start with an empty string.
2. Iterate through each digit: For each digit, retrieve the corresponding string of characters from the mapping array.
3. Combine: For each character in the string, combine it with each existing combination.
4. Update the combinations: At each step, update the current combinations with the new ones.
5. Return the result: Once all digits have been processed, return the list of combinations.

This approach efficiently generates all the combinations by leveraging the power of iteration and the BFS method of building combinations incrementally.

🎯 Conclusion

The letterCombinations method is a great example of solving a combinatorial problem using an iterative approach with a BFS-like pattern. The algorithm efficiently constructs all possible combinations of letters for the given input string of digits, and is a classic use case for building combinations from a fixed set of possibilities.

With this understanding, you can apply the same approach to similar problems that require generating combinations or permutations from a set of choices.