Java DFS solution with stringbuilder


  • 0
    Q
    public class Solution {
        // Straight forward solution, store the keys into a hash, then recursively create the permutations
        // O(3^n)
        // The reason why this is a 3^n is because there are 3^n solutions in the list.
        
        private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<>();
            solve (result, digits, 0, new StringBuilder());
            return result;
        }
        
        public void solve (List<String> result, String digits, int index, StringBuilder sb) {
            if (sb.length() == digits.length()) {
                if (sb.length() != 0) {
                    result.add(sb.toString());
                }
                return;
            }
    
           String s = KEYS[digits.charAt(index) - '0'];
           for (int i = 0; i < s.length(); i++) {
               sb.append(s.charAt(i));
               solve(result, digits, index+1, sb);
               sb.setLength(sb.length()-1);
           }
        }
        
    }
    

Log in to reply
 

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