Iterative c++ solution in 0ms


  • 60
    A
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(digits.empty()) return vector<string>();
        static const vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        result.push_back("");   // add a seed for the initial case
        for(int i = 0 ; i < digits.size(); ++i) {
            int num = digits[i]-'0';
            if(num < 0 || num > 9) break;
            const string& candidate = v[num];
            if(candidate.empty()) continue;
            vector<string> tmp;
            for(int j = 0 ; j < candidate.size() ; ++j) {
                for(int k = 0 ; k < result.size() ; ++k) {
                    tmp.push_back(result[k] + candidate[j]);
                }
            }
            result.swap(tmp);
        }
        return result;
    }
    

    Simple and efficient iterative solution.

    Explanation with sample input "123"

    Initial state:

    • result = {""}

    Stage 1 for number "1":

    • result has {""}
    • candiate is "abc"
    • generate three strings "" + "a", ""+"b", ""+"c" and put into tmp,
      tmp = {"a", "b","c"}
    • swap result and tmp (swap does not take memory copy)
    • Now result has {"a", "b", "c"}

    Stage 2 for number "2":

    • result has {"a", "b", "c"}
    • candidate is "def"
    • generate nine strings and put into tmp,
      "a" + "d", "a"+"e", "a"+"f",
      "b" + "d", "b"+"e", "b"+"f",
      "c" + "d", "c"+"e", "c"+"f"
    • so tmp has {"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" }
    • swap result and tmp
    • Now result has {"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" }

    Stage 3 for number "3":

    • result has {"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" }
    • candidate is "ghi"
    • generate 27 strings and put into tmp,
    • add "g" for each of "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"
    • add "h" for each of "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"
    • add "h" for each of "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"
    • so, tmp has
      {"adg", "aeg", "afg", "bdg", "beg", "bfg", "cdg", "ceg", "cfg"
      "adh", "aeh", "afh", "bdh", "beh", "bfh", "cdh", "ceh", "cfh"
      "adi", "aei", "afi", "bdi", "bei", "bfi", "cdi", "cei", "cfi" }
    • swap result and tmp
    • Now result has
      {"adg", "aeg", "afg", "bdg", "beg", "bfg", "cdg", "ceg", "cfg"
      "adh", "aeh", "afh", "bdh", "beh", "bfh", "cdh", "ceh", "cfh"
      "adi", "aei", "afi", "bdi", "bei", "bfi", "cdi", "cei", "cfi" }

    Finally, return result.


  • 0
    H

    It is very smart to use the swap() method.
    Concise and high performance.


  • 0
    N

    AHaaaaaaaaaaaaaaa,swap() is so great!


  • 0
    R

    Really smart.I thought out almost the same method but I used std::move() instead.


  • 0
    O

    Like this one. swap is neat here.


  • 8
    Y

    Sample input is supposed to be "234"?


  • 0
    V

    like Permutations by BFS , every iteration create a new buffer which substitute the last one .


  • 1
    C

    I learned a lot from this, great solution, thanks for sharing!


  • 0
    M

    Amazing swap() technique.


  • 1
    R

    What is the time complexity of that solution?


  • 0
    G

    Explanation with sample input "123" is supposed to be "234"?


  • 0
    B

    I'm confused about the swap() part. Why do we need the swap? What if we just use result = tmp; there? I did this and it said accepted.
    I think every iteration we have a new tmp, I don't know why the swap is necessary.
    Someone please help me!


Log in to reply
 

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