Java -- backtracking solution


  • 0
    J

    This is my backtracking solution.

    public class Solution {
        public List<String> letterCombinations(String digits) {
            String[] keys = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
            List<String> result = new ArrayList<>();
            backtrack(result, "", keys, digits, 0);
            return result;
        }
        
        private void backtrack(List<String> result, String s, String[] keys, String digits, int start) {
            if (digits.isEmpty())
                return;
            if (s.length() == digits.length())
                result.add(s);
            else {
                for (int i = start; i < digits.length(); i++) {
                    int index = digits.charAt(i) - '0';
                    for (int j = 0; j < keys[index].length(); j++) {
                        s = s + keys[index].charAt(j);
                        backtrack(result, s, keys, digits, i + 1);
                        s = s.substring(0, s.length() - 1); 
                    }
                }
            }
        } 
    }
    

  • 1
    S

    I don't know why you set this to O(n * m ^2) complexity because in your way, code like this will be enough

        public List<String> letterCombinations(String digits) {
            String[] map = new String[]{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            List<String> r = new ArrayList<>();
            if (digits.equals("")) return r;
            search(digits, 0, "", r, map);
            return r;
        }
    
        public void search(String digits, int start, String prefix, List<String> lst, String[] map) {
            if (prefix.length() == digits.length()) {
                lst.add(prefix);
                return;
            }
            char digit = digits.charAt(start);
            char[] chars = map[digit - '0'].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                search(digits, start + 1, prefix + chars[j], lst, map);
            }
        }

Log in to reply
 

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