StringBuildersb=newStringBuilder(); for (inti=0; i < len; i++) { sb.append("a"); }
for (inti=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 (intj=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 (intk=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 (intl=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(4N)
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.
for (String item : res) { for (char curDigit : curLetters.toCharArray()) { newRes.add(item + curDigit); } }
res = newRes; }
return res; }
Analysis
Time Complexity: O(3M×4N)
Space Complexity: O(3M×4N)
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.