Java solution beats 100% time


  • 0
    K

    The idea is to create a 2D char Array for all the digits in the input. e.g. for input "37" the Array should be :
    [ ['d', 'e', 'f'], ['p', 'q', 'r', 's'] ]
    and an index Array [0,0] to track the current index of each input array.
    Note: both array size is equal to the input length.

    Now add the characters from the char Array based on the current index in the index Array and always increment the last item of the index Array by 1. If that value overflows then make it 0 and try to increment the previous item in the array and so on ..

    Once the 1st item of the index array overflows, you have all the combinations accumulated.

    class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<String>();
            if(digits.isEmpty()){
                return result;
            }
            int n = digits.length();
            char[][] lookup = new char[n][];
            for(int i=0; i<digits.length(); i++){
                int d = Integer.parseInt(digits.substring(i, i+1));
                int start = 97 + (d-2)*3;
                if(d > 7)
                    start++;
                int inc = (d == 7 || d == 9)? 4 : 3;
                lookup[i] = new char[inc];
                for(int j = 0; j < inc; j++){
                    lookup[i][j] = (char)start++;
                }
            }
            
            int[] indexArr = new int[n];
            StringBuilder sb;
            while(true){
                sb = new StringBuilder();
                for(int i=0; i<n; i++){
                    sb.append(lookup[i][indexArr[i]]);
                }
                result.add(sb.toString());
                
                if(indexArr[n-1]+1 < lookup[n-1].length){
                    indexArr[n-1]++;
                    continue;
                }
                indexArr[n-1] = 0;
                int ptr = n-2;
                boolean end = true;
                
                while(ptr >= 0){
                    if(indexArr[ptr]+1 < lookup[ptr].length){
                        indexArr[ptr]++;
                        end = false;
                        break;
                    }
                    indexArr[ptr] = 0;
                    ptr--;
                }
                if(end){
                    break;
                }
            }
            
            return result;
        }
    }
    
    

Log in to reply
 

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