> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-13-2022-17.md).

# 02/13/2022 17

Method:

1. If the input is empty, return an empty array.
2. Initialize a string array that maps digits to their letters
3. Use a backtracking function to generate all possible combinations.

Time O(N \* 4^N) worst case

Space O(n)

时间复杂度：O(3^m×4^)，其中 mm 是输入中对应 33 个字母的数字个数（包括数字 22、33、44、55、66、88），n 是输入中对应 44 个字母的数字个数（包括数字 77、99），m+n 是输入数字的总个数。当输入包含 mm 个对应 33 个字母的数字和 nn 个对应 44 个字母的数字时，不同的字母组合一共有 3^m \times 4^n3 m ×4 n 种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 mm 是输入中对应 33 个字母的数字个数，nn 是输入中对应 44 个字母的数字个数，m+nm+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+nm+n。

作者：LeetCode-Solution 链接：<https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/> 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

* The function should take 2 primary inputs: the current combination of letters we have, `path`, and the `index` we are currently checking.
* As a base case, if our current combination of letters is the same length as the input `digits`, that means we have a complete combination. Therefore, add it to our answer, and backtrack.
* Otherwise, get all the letters that correspond with the current digit we are looking at, `digits[index]`.
* Loop through these letters. For each letter, add the letter to our current `path`, and call `backtrack` again, but move on to the next digit by incrementing `index` by 1.
* Make sure to remove the letter from `path` once finished with it.

```
class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) return result;
        String[] numToString = {"","", "abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtracking(numToString, digits, 0);
        return result;      
    }
    private void backtracking(String[] numToString, String digits, int index){
        //base condition
        if(path.length() == digits.length()){
            result.add(path.toString());
            return;
        }
        
        String check = numToString[digits.charAt(index) - '0'];
        
        for (int i = 0; i < check.length(); i++){
            // Add the letter to our current path
            //int length = path.length();
            path.append(check.charAt(i));
            // Move on to the next digit
            backtracking(numToString, digits, index + 1);
            // Backtrack by removing the letter before moving onto the next
            path.deleteCharAt(path.length() - 1);
            //path.setLength(length);
        }
    }
}
```

}

In the brute force solution, the number of nested for loops depends on the input size. So you just cannot write it.

**求不同集合之间的组合**

注意：输入1 \* #按键等等异常情况

代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。

Map\<Character, String> letters = Map.of( '2', "abc", '3', "def", '4', "ghi", '5', "jkl", '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");

* Time complexity: O(4^N \cdot N)O(4N⋅N), where NN is the length of `digits`. Note that 44 in this expression is referring to the maximum *value* length in the *hash map*, and ***not*** to the length of the *input*.

  The worst-case is where the input consists of only 7s and 9s. In that case, we have to explore 4 additional paths for every extra digit. Then, for each combination, it costs up to NN to build the combination. This problem can be generalized to a scenario where numbers correspond with up to MM digits, in which case the time complexity would be O(M^N \cdot N)O(MN⋅N). For the problem constraints, we're given, M = 4M=4, because of digits 7 and 9 having 4 letters each.
* Space complexity: O(N)O(N), where NN is the length of `digits`.

  Not counting space used for the output, the extra space we use relative to input size is the space occupied by the recursion call stack. It will only go as deep as the number of digits in the input since whenever we reach that depth, we backtrack.

  As the hash map does not grow as the inputs grows, it occupies O(1)O(1) space.

```
 public class Solution {
        public static List<String> letterCombinations(String digits) {
            String digitletter[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            List<String> result = new ArrayList<String>();
    
            if (digits.length()==0) return result;
            
            result.add("");
            for (int i=0; i<digits.length(); i++) 
                result = combine(digitletter[digits.charAt(i)-'0'],result);
            
            return result;
        }
        
        public static List<String> combine(String digit, List<String> l) {
            List<String> result = new ArrayList<String>();
            
            for (int i=0; i<digit.length(); i++) 
                for (String x : l) 
                    result.add(x+digit.charAt(i));
    
            return result;
        }
    }
```

<https://leetcode.com/problems/letter-combinations-of-a-phone-number/discuss/8064/My-java-solution-with-FIFO-queue>

```
public List<String> letterCombinations(String digits) {
		LinkedList<String> ans = new LinkedList<String>();
		if(digits.isEmpty()) return ans;
		String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
		ans.add("");
		for(int i =0; i<digits.length();i++){
			int x = Character.getNumericValue(digits.charAt(i));
			while(ans.peek().length()==i){
				String t = ans.remove();
				for(char s : mapping[x].toCharArray())
					ans.add(t+s);
			}
		}
		return ans;
	}
```

```
public List<String> letterCombinations(String digits) {
		LinkedList<String> ans = new LinkedList<String>();
		if(digits.isEmpty()) return ans;
		String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
		ans.add("");
		while(ans.peek().length()!=digits.length()){
			String remove = ans.remove();
			String map = mapping[digits.charAt(remove.length())-'0'];
			for(char c: map.toCharArray()){
				ans.addLast(remove+c);
			}
		}
		return ans;
	}
```

while(ans.peek().length()==i){ //View the length of the top element of the LinkedList String t = ans.remove(); //move each element out for(char s : mapping\[x].toCharArray()) //Traversing x corresponding string of characters ans.add(t+s); //add s to t,as "a"+"d"="ad" }