```
public class Solution {
// Straight forward solution, store the keys into a hash, then recursively create the permutations
// O(3^n)
// The reason why this is a 3^n is because there are 3^n solutions in the list.
private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
solve (result, digits, 0, new StringBuilder());
return result;
}
public void solve (List<String> result, String digits, int index, StringBuilder sb) {
if (sb.length() == digits.length()) {
if (sb.length() != 0) {
result.add(sb.toString());
}
return;
}
String s = KEYS[digits.charAt(index) - '0'];
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
solve(result, digits, index+1, sb);
sb.setLength(sb.length()-1);
}
}
}
```