My 0ms C++ Permutation Result with Explanation


  • 0
    Y
    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> res;
            if (digits.size() == 0) return res;
            vector<string> dic = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            vector<string> permutation;
            for (int i = 0; i < digits.size(); i++)         
                permutation.push_back(dic[digits[i]-'0']);
            //An permutation Algorithm using "different-carry-number"    
            vector<int> index(permutation.size(),0);
            while (true) {
                string resStr;// organize word
                for (int i = 0; i < permutation.size();i++) {
                    resStr += permutation[i][index[i]];
                }
                res.push_back(resStr);// add word to string
                index[index.size()-1]++;
                for(int i = permutation.size()-1; i >= 0; i--) {// check carry
                    if(index[0] == permutation[0].size()) return res;
                    if(index[i] == permutation[i].size()) {
                        index[i] = 0;
                        index[i-1]++;
                    }
                }
            }
        }
    };
    

Log in to reply
 

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