My concise JAVA solution based on DFS with explanation


  • 2

    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);
    }

Log in to reply
 

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