> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/untitled-1.md).

# 17. Letter Combinations of a Phone Number

{% hint style="info" %}
DFS
{% endhint %}

```java
class Solution {
    private static String[] keys = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> result = new LinkedList<String>();
        findConbinations(result, 0, digits, "");
        return result;
    }
    
    private void findConbinations(List<String> list, int index, String digits, String str){
        if (digits.length() == 0) return;
        if(index == digits.length()){
            list.add(str);
        }else{
            String key = keys[digits.charAt(index)-'0'];
            for(int i =0; i<key.length(); i++){
                // here, str+key.charAt(i) generates a new string object;
                findConbinations(list, index+1, digits, str+key.charAt(i));
            }
        }
    }
}
```