# Title Description (medium difficulty)

Given a string of numbers, each number can represent several letters under the number key, and return all the possible composition of the letters under these numbers.

# Solution 1 multiplication of definitions

I thought about using iteration and recursion, but I couldn't figure it out. I came up with this algorithm.

Consider the string "23" as ["a","b",c] * ["d","e","f"], and the multiplication can be realized by two for loops. You can see the code.

``````public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<String>();
for (int i = 0; i < digits.length(); i++) {
ans = mul(ans, getList(digits.charAt(i) - '0'));
}
return ans;

}

public List<String> getList(int digit) {
String digitLetter[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> ans = new ArrayList<String>();
for (int i = 0; i < digitLetter[digit].length(); i++) {
}
return ans;
}
//Defined as multiplication of two lists
public List<String> mul(List<String> l1, List<String> l2) {
if (l1.size() != 0 && l2.size() == 0) {
return l1;
}
if (l1.size() == 0 && l2.size() != 0) {
return l2;
}
List<String> ans = new ArrayList<String>();
for (int i = 0; i < l1.size(); i++)
for (int j = 0; j < l2.size(); j++) {
}
return ans;
}``````

# Solution two queue iteration

Reference resources Here , someone wrote it in iteration. Mainly used the queue.

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

If it's 23, then

At the end of the first for cycle, it becomes a, b, c;

In the first time of the second for cycle, when cycle a is out of the team, d e f is added respectively and then in the team, it becomes b c ad ae af

In the second for cycle, the second while cycle b is out of the team, adding d e f to it, and then entering the team, it becomes c ad ae af bd be bf

The third while cycle c of the second for cycle is out of the team, adding d e f to it and then entering the team, it becomes ad AE AF BD be BF c D CE CF

In this way, when the queue element length is no longer equal to 1, a while loop will appear.

# Solution three recursion

Reference resources Here

``````private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

public List<String> letterCombinations(String digits) {
if(digits.equals("")) {
return new ArrayList<String>();
}
combination("", digits, 0, ret);
return ret;
}

private void combination(String prefix, String digits, int offset, List<String> ret) {
//offset represents which number to add
if (offset == digits.length()) {
return;
}
String letters = KEYS[(digits.charAt(offset) - '0')];
for (int i = 0; i < letters.length(); i++) {
combination(prefix + letters.charAt(i), digits, offset + 1, ret);
}
}
``````