3
\$\begingroup\$

In preparation for interviews, I have written a solution to this question:

Given a sequence of numbers (34128) and an input map such as a dial pad on a phone (2->[a,b,c], 3->[d,e,f], 4->[g,h,i]) write an algorithm to return all possible words from the sequence. E.g. Input: 232 Output: [ada, adb, adc, aea, aeb, aec, afa, afb, afc, bda, bdb, bdc, bea, beb, bec, bfa, bfb, bfc, cda, cdb, cdc, cea, ceb, cec, cfa, cfb, cfc]

Also what will happen if this would have been a 12 digit international number? How would that effect your design.

Below is the solution I have:

public class DialPad {

    public static void main(String[] args) {
        System.out.println(letterCombinations("232"));
    }

    public static ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for (int i = 0; i < digits.length(); i++) {
            for (String str : res) {
                String letters = map.get(digits.charAt(i));
                for (int j = 0; j < letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList<String>();
        }
        return res;
    }

    static final HashMap<Character, String> map = new HashMap<Character, String>() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };
}

Is there any improvement I can make here? It looks to me like complexity is high in this code. How can I simplify this code better?

\$\endgroup\$
4
\$\begingroup\$

Putting the members of this class in the reverse order (map, then letterCombinations(), then main()) would be more customary. The map should be private unless you have a good reason to do otherwise. I would also avoid creating an anonymous subclass of HashMap, and initialize it this way:

private static final HashMap<Character, String> map = new HashMap<>(8);
static {
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
};

It would be more obvious that preres is a temporary variable if you scoped it properly. Both res and preres could be named better — I've chosen results and nextResults, respectively.

Whenever possible, you should specify the initial capacity of an ArrayList. The penalty for underestimating can be rather severe, as it requires reallocating and copying existing results.

digits.charAt(i) is a loop invariant that can be moved from the middle loop into the outer one.

All loops should have braces. Omitting them is bad practice and will cause maintenance-induced bugs.

public static List<String> letterCombinations(String digits) {
    List<String> results = new ArrayList<String>();
    results.add("");

    for (int i = 0; i < digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        List<String> nextResults = new ArrayList<>(letters.length() * results.size());
        for (String str : results) {
            for (int j = 0; j < letters.length(); j++) {
                nextResults.add(str + letters.charAt(j));
            }
        }
        results = nextResults;
    }
    return results;
}

It's generally better to return List<String> rather than ArrayList<String>, to give you flexibility to change the implementation. For example, here is a solution that uses just one LinkedList.

public static List<String> letterCombinations(String digits) {
    LinkedList<String> results = new LinkedList<>();
    results.add("");

    for (int i = 0; i < digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        for (int j = results.size(); j > 0; j--) {
            String intermediateResult = results.poll();
            for (int k = 0; k < letters.length(); k++) {
                results.add(intermediateResult + letters.charAt(k));
            }
        }
    }
    return results;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the help. Is there any way we can reduce the complexity - as of now it is O(n^3) right? \$\endgroup\$ – david May 24 '15 at 20:44
  • 1
    \$\begingroup\$ \$O(n^3)\$ is a gross underestimate. For a digits string of length \$n\$, we expect at least \$3^n\$ results — more if 7 is involved. Therefore, the optimal complexity is \$O(4^n)\$. \$\endgroup\$ – 200_success May 24 '15 at 20:50
2
\$\begingroup\$

Refer to objects by their interfaces

Something that sticks in the eye is the ArrayList and HashMap in type declarations. You should use interface types instead, for example:

static List<String> letterCombinations(String digits) { ... }

Naming

The names are not great. I guess "res" stands for "results". "results" is not much longer, but a bit clearer still. "preres" is not clear at all.

Performance

Although your implementation does the job, keep in mind its weaknesses:

  • High memory usage: it accumulates all the combinations in one giant list
  • Lots of temporary objects: in the process of building all the combinations, there's a lot of string concatenation, and therefore lots of temporary objects until reaching the completed versions

To improve that, you would need a completely different algorithm.

To avoid keeping all the results in memory, you would need a different approach entire, something that doesn't store all combinations in memory at the same time.

For example, you could use an iterator pattern, where the iterator spits out the possible combinations in a predefined order, and without accumulating results internally.

Consider this sequence:

 0,   1,   2,   3,   4,   5,   6,  ...
ada, adb, adc, aea, aeb, aec, afa, ...

You can think of ada, adb, ... as numbers in a numbering system:

a d a
0 0 0 = 0

a d b
0 0 1 = 0 + 0 + 1

a d c
0 0 2 = 0 + 0 + 2

a e a
0 1 0 = 0 + 1 * 3 + 0 = 3

...

a f b
0 2 1 = 0 + 2 * 3 + 1 = 7

...

The iterator would store its state in a simple counter, and when a next element is requested, increment the counter, and return the string that corresponds to the number in this alternative numbering system.

Note that the counting is not base-3. If all numbers had 3 possible letters, it would be base-3 and not too complicated. But some numbers have 4 possible letters. So, unfortunately, it's quite complicated.

\$\endgroup\$
  • \$\begingroup\$ A complication with the counting system is that "pqrs" is four letters, so you it's not quite base 3. \$\endgroup\$ – 200_success May 24 '15 at 20:38
  • \$\begingroup\$ That's why I never said it's base 3 ;-) I added a note at the end to clarify. \$\endgroup\$ – janos May 24 '15 at 20:49
0
\$\begingroup\$

I solved this using the simple route. Basically, I used switch statement first..

public static char[] getChars(char s){
    switch(s){
    case '1':
        char[] one = {};
        return one;

    case '2':
        char[] two = {'a','b','c'};
        return two;

    case '3':
        char[] three = {'d','e','f'};
        return three;
    // did this for all...  

    case '0':
        char[] zero = {' '};
        return zero;

    }
    return null;
}

Next just perform permutation.. and you're good to go

public static void perm(long val){
    perm("",String.valueOf(val));
}

private static void perm(String pre, String sur){
    if(sur.length() == 0){
        System.out.println(pre);
    }else{
        char[] chars = getChars(sur.charAt(0));
        if(chars.length > 0){
            for(char c: chars){
                perm(pre + c, sur.substring(1));
            }
        }else{
            perm(pre,sur.substring(1));
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for providing an actual review with your second answer. However, this answer still leans toward code-only. If you could explain how this is better than the asker's code, then that will really help. \$\endgroup\$ – Jamal May 25 '15 at 19:04
  • \$\begingroup\$ You've provided an alternative implementation. Since this site is Code Review, could you explain how your solution is better than the original code? \$\endgroup\$ – 200_success May 25 '15 at 19:05
  • \$\begingroup\$ Basically I think this code is much simpler than the asker's code. Since the asker asked for a simpler implementation. @Jamal \$\endgroup\$ – AyoFafore May 25 '15 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.