Java DFS solution


  • 0
    K
    public class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> res = new ArrayList<String>();
            String[] chars = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            dfs(digits, 0, new StringBuilder(), chars, res);
            return res;
        }
        
        private void dfs(String digits, int startIdx, StringBuilder cur, String[] chars, List<String> res) {
            if(cur.length() == digits.length() && startIdx != 0) {
                res.add(cur.toString());
                return;
            }
            
            for(int i = startIdx; i < digits.length(); ++i) {
                int idx = digits.charAt(i)-'0';
                if(idx < 2 || idx >9) continue;
                for(int j = 0; j < chars[idx].length(); ++j) {
                    char c = chars[idx].charAt(j);
                    cur.append(c);
                    dfs(digits, i+1, cur, chars, res);
                    cur.deleteCharAt(cur.length()-1);
                }
            }
        }
    }
    

Log in to reply
 

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