My very clear DFS solution from USC


  • 0
    Z

    public class Solution {
    public List<String> letterCombinations(String digits) {

        List<String> list = new ArrayList<String>();
        if (digits == null || digits.length() == 0) {
            return list;
        }
        
        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");
        map.put(0, "");
        dfs(list, digits, 0, "", map);
        return list;
    }
    
    private void dfs(List<String> list, String digits, int index, String str, Map<Integer, String> map) {
        
        String temp_str = str;
        if (temp_str.length() == digits.length()) {
            //System.println(temp_str);
            list.add(temp_str);
            return;
        }
        
        Integer j = Character.getNumericValue(digits.charAt(index));
        String map_str = map.get(j);
        //System.out.println(map_str);
        for (int i = 0; i < map_str.length(); i++) {
            temp_str = temp_str + Character.toString(map_str.charAt(i));
            dfs(list, digits, index + 1, temp_str, map);
            temp_str = temp_str.substring(0, temp_str.length() - 1);
        }
    }
    

    }


  • 0
    Z

    @zongtb you are master, I want to birth a monkey to you


Log in to reply
 

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