By Long Luo

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.

## 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.

## Analysis

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

# BFS

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

## 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.

## 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. 😉😃💗