Java 3ms solution, beats 79.73%


  • 0
    C

    Would love to gain some criticism on the bottlenecks of this code. Wondering how it can run faster. This is essentially running DFS.

    public class Solution {
        char[][] alpha = new char[][] {{'a','b','c'},
                                  {'d','e','f'},
                                  {'g','h','i'},
                                  {'j','k','l'},
                                  {'m','n','o'},
                                  {'p','q','r','s'},
                                  {'t','u','v'},
                                  {'w','x','y','z'}};
        public List<String> letterCombinations(String digits) {
            List<String> ret = new ArrayList<String>((int)Math.pow(3,digits.length())); // At least this size
            if (digits == null || digits.length() == 0) {
                return ret;
            }
            char[] d = digits.toCharArray(),
                   s = new char[d.length];
            _comboMe(ret,d,s,0);
            return ret;
        }
        
        private void _comboMe(List<String> l, char[] digits, char[] string, int index) {
            int dval = digits[index] - 50; // offset ascii 48 by 2
            for(int i=0;i<alpha[dval].length;i++) {
                string[index] = alpha[dval][i];
                if (index + 1 == string.length) {
                    l.add(new String(string));
                } else {
                    _comboMe(l,digits,string,index+1);
                }
            }
        }
    }
    

Log in to reply
 

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