Java easy to understand recursive solution.


  • 2
    C
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<Character, String>(){{
            put('2', "abc"); put('3', "def"); put('4', "ghi"); put('5', "jkl");
            put('6', "mno"); put('7', "pqrs"); put('8', "tuv"); put('9', "wxyz");
        }};
        List<String> ret = new ArrayList<>();
        if (digits.equals("")) {
            return ret;
        }
        dfs(digits, 0, "", map, ret);
        return ret;
    }
    
    private void dfs(String digits, int idx, String path, Map<Character, String> map, List<String> ret) {
        if (digits.length() == path.length()) {
            ret.add(path);
            return;
        }
        for (int i = idx; i < digits.length(); i++) {
            for (char c: map.get(digits.charAt(i)).toCharArray()) {
                dfs(digits, i+1, path+c, map, ret);
            }
        } 
    }

  • 0

    I believe you might want to double check whether there are duplicates in the ret:

    if ( path.length() == digits.length() ) {
                if (!ret.contains(element)) {
                ret.add(new String(element));}
                return;
            }
    

  • 0
    B

    @Juan55555 Actually, he don't have to. Because it is impossible to have two same str at the end of the recursion. I think "ba" and "ab" are not same answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.