Iterative Java solution


  • 1
    S

    Hi guys!

    I've decided to experiment with different approach than backtracking and recursion. It reminds a bit radix-sort style. The main idea is to keep a buffer of chars representing the word. At first it is initiated by first letter from the corresponding mapping list for each digit. Then we sequentially try all letters of a first digit. Then "increment" letter for the second digit, and run through all first ones again. Etc. Like spinning the rings of a number lock.

    public class Solution {
        
        private static final Map<Character, String> mapping = new HashMap<>();
        static { 
            mapping.put('2', "abc"); mapping.put('3', "def"); 
            mapping.put('4', "ghi"); mapping.put('5', "jkl"); 
            mapping.put('6', "mno"); mapping.put('7', "pqrs");
            mapping.put('8', "tuv"); mapping.put('9', "wxyz");
        }
        
        public List<String> letterCombinations(String digits) {
            if (digits.isEmpty()) return Arrays.asList("");
            List<String> res = new LinkedList<>();
            // init our buffer with first letters for each digit
            char[] buf = new char[digits.length()];
            for (int k = 0; k < buf.length; k++) 
                    buf[k] = mapping.get(digits.charAt(k)).charAt(0);
            // array of current letter's indices for each position
            int[] idx = new int[digits.length()];
            int i = 0;
            while (i < digits.length()) {
                res.add(new String(buf)); // add the current buffer to the result
                i = 0;
                // run through positions incrementing the corresponding index,
                // there could be two cases:
                // 1. we tried all letters at this position -> we must reset it and
                //     move to the next one;
                // 2. we find the position where we didn't try all, so we just
                //     increment corresponding index and break the loop,
                //     because we actually found the next combination.
                while (i < digits.length()) {
                    idx[i] = (idx[i] + 1) % mapping.get(digits.charAt(i)).length();
                    buf[i] = mapping.get(digits.charAt(i)).charAt(idx[i]);
                    if (idx[i] != 0) break;
                    i++;
                }
            }
            return res;
        }
    }
    

    Actually, this approach looks more effective than recursive search not only because it's iterative but also because we reuse the tail of our buffer making some kind of memoization.

    Have a nice one!


  • 0
    F

    hey man, I ran your code just now. Answer is correct, but you didn't use any kind of memorization. each time you created a new String you modified every index of the "buf" rather than held those do not need to change. So your solution is much slower than backtracking.


  • 0
    S

    Hey! You're right that we create a new string for each new combination. But in backtracking solution we still need to create them because it's java and we can't reuse the same chars. But if you mean that we change each letter in the buffer, that's not true - we break the while loop when we find the position of "no overflowing" increment and the remaining part stays unchanged. But I will try to compare this solution and the one using backtracking with some benchmarks a bit later. Thanks for remark!


  • 0
    S

    Hey man! I compared my method with backtracking approach through a very rough benchmark and it appeared to be four times faster.

    Solver: backtracking, time: 4838 ms

    Solver: iterative, time: 1106 ms

    Of course, I could implement backtracking in not the most effective way, but anyway here's the code: https://gist.github.com/andreytim/825416e36a94b4910277#file-letter_comb-java


  • 0
    F

    sry man I didn't see your reply these days. I run your solution on my IDE too, It's also more than twice faster than my backtracking. I misunderstood your code, that's my fault ^ ^


Log in to reply
 

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