**Explanation**

The basic idea is using DFS to get the letter permutation for the corresponding input digit string. In the regular DFS algorithm, we need a boolean visited array to avoid duplicated permutation. But in this case, the loop keeps going without backtracking, so visited array is not necessary.

```
public List<String> letterCombinations(String digits) {
List<String>res = new LinkedList<String>();
if (digits == null || digits.isEmpty()) return res;
final String map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"};
DFS(digits.toCharArray(), 0, "", res, map);
return res;
}
private void DFS(char digits[], int cur, String solution, List<String>res, String[] map) {
if (cur == digits.length) {
res.add(solution);
return;
}
int digit = digits[cur] - '0';
for (int i = 0; i < map[digit].length(); i++)
// Permutation with the characters in map corresponding to the specific digit.
DFS(digits, cur + 1, solution + map[digit].charAt(i), res, map);
}
```