### Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

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

``````import java.util.ArrayList;
import java.util.List;

/**
* Created by gzdaijie on 16/5/18
* 递归,每一个数字有3-4种情况,遇到每一个数字,遍历其所有可能性即可
*/
public class Solution {
private static final String[] strs = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
StringBuilder combine = new StringBuilder();

if (digits == null || digits.length() == 0) return result;

letterFullPemutation(result, digits, combine, 0);
return result;
}

/**
* @param result 存储结果
* @param str 输入的数字
* @param combine  临时变量,存储当前拼接的字符串
* @param k 表示当前已经遍历到的位置
*/
private void letterFullPemutation(List<String> result, String str, StringBuilder combine, int k) {
// 如果遍历完,而且拼接的字符串不为空,则加入结果当中
if (k == str.length()) {
if (combine.length() > 0) {
}
return;
}

int index = str.charAt(k) - '2';
if (index < 0) {
letterFullPemutation(result, str, combine, k + 1);
} else {
int len = strs[index].length();
for (int i = 0; i < len; i++) {
combine.append(strs[index].charAt(i));
letterFullPemutation(result, str, combine, k + 1);
combine.setLength(combine.length() - 1);
}
}
}
}
``````
``````import java.util.*;

/**
* Created by gzdaijie on 16/5/18
* BFS，使用队列实现，每次出队的子串，依次添加当前数字对应的字母，再入队
*/
public class Solution {
private static final String[] strs = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return new ArrayList<>(result);

String str = strs[digits.charAt(0) - '2'];
int len = str.length();
for (int i = 0; i < len; i++) {
}

for (int i = 1; i < digits.length(); i++) {
int size = result.size();
while (size-- > 0) {
String prefix = result.poll();
str = strs[digits.charAt(i) - '2'];
len = str.length();
for (int j = 0; j < len; j++) {