My java solution with FIFO queue


  • 383
    L
        public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        for(int i =0; i<digits.length();i++){
            int x = Character.getNumericValue(digits.charAt(i));
            while(ans.peek().length()==i){
                String t = ans.remove();
                for(char s : mapping[x].toCharArray())
                    ans.add(t+s);
            }
        }
        return ans;
    }

  • 6
    F

    amazing! how did you come up with this solution~


  • 17
    R

    If you think about the recursive solution similar to a DFS approach, then this would be the equivalent BFS solution (using a queue).


  • 11
    D

    Did you consider 0, 1 as valid input and output results with 0 and 1? I think the problem asked for letter combinations so 0 and 1 should be ignored.


  • 56
    Y

    Very good solution!! Thumb up!
    This is a iterative solution. For each digit added, remove and copy every element in the queue and add the possible letter to each element, then add the updated elements back into queue again. Repeat this procedure until all the digits are iterated.

    I did a experiment to compare backtracking(DFS) method and this iterative method. It turns out iterative one is 4 times faster.

    One minor bug here.
    We need to add some code to test whether the input is empty or not.
    Above ans.add("");
    add

    if (digits.length()==0){
    	return ans;
    }

  • 6

    I have a different approach and it is more intuitive to me. This is similar to printing all numbers with k digits. For example k=3, you start at 000, then you keep coming up: 001, 002, 003, ... until you reach 009, then reset last bit, and increase the next bit to 010, then 011, 012, etc.

    So we can solve this problem in a similar way. If our input string is "23". Because 2 = "abc", 3 = "def", we can start from the smallest "ad", then go up: "ae", "af", then we have to reset last char from "f" to "d" and we have "bd", "be", "bf", etc. This way, we don't need backtracking, recursive, or List.

    Hope this helps for some people.

    vector<string> letterCombinations(string digits) {
        vector<string> R;
        if (digits.empty()) return R;
        string a[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        int n = digits.size();
        vector<int> v(n, 0);
        
        // Initialize string V
        string S = "";
        for (int i=0; i<n; i++)
            S += a[digits[i]-'0'-2][0];
        
        while (true) {
            R.push_back(S);
            int j = n-1;
            v[j]++;
            while (j>0 && v[j]==a[digits[j]-'0'-2].size()) {
                v[j] = 0;
                S[j] = a[digits[j]-'0'-2][0];
                v[--j]++;
            }
            
            //Check to see if outta range yet
            if (v[0]==a[digits[0]-'0'-2].size()) break;
            else S[0] = a[digits[0]-'0'-2][v[0]];
            
            S[j] = a[digits[j]-'0'-2][v[j]];
        }
        return R;
    }

  • 5
    T

    Good solution. Thumbs up.
    why can't I think of something like this. :(


  • 1
    T

    Freaking Genius !!


  • 0

    when ans is empty why 'ans.peek().length()' does not pop up exception?
    I thought ans.peek() will get null.


  • 0

    That's right!!


  • 13
    V

    very 66666 !!!


  • 0
    A

    how can you come up with that!


  • 4
    K

    Need to add
    LinkedList<String> ans = new LinkedList<String>();
    if(digits == null || digits.length() == 0) return ans;
    or the submission will fail. I guess new corner cases have been added


  • 0
    H

    ans.peek() returns ""


  • 4
    S

    vote for

    while(list.peek().length() == i)

  • 8
    N

    It could be slightly faster if you use:

    int x = digits.charAt(i) - '0';

  • 0
    X

    Amazing! Great job dude!


  • 0
    T

    I tested it in OJ, results in error


  • 3
    A

    Nice code, btw, your answer will not be AC if digits == "", so should add the corner case
    if (digits == null || digits.length() == 0) {
    return res;
    }


  • 6
    C

    C# implementation based on same idea

    private static string[] mapping = new string[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        
    public IList<string> LetterCombinations(string digits) {
        if (digits.Length == 0)
        {
            return new List<string>();
        }
        
        Queue<string> ans = new Queue<string>();
        
        ans.Enqueue("");
        for (int i = 0; i < digits.Length; i++)
        {
            int x = digits[i] - '0';
            while (ans.Peek().Length == i)
            {
                String t = ans.Dequeue();
                foreach (char s in mapping[x])
                    ans.Enqueue(t + s);
            }
        }
        
        return ans.ToList();
    } 

Log in to reply
 

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