C++ BFS solution


  • 0
    C
    class Solution {
    public:
    
        vector<string> letterCombinations(string digits) 
        {
            if(digits.size() == 0)
                return vector<string>();
            unordered_map<int, string> digitToLetters;
            digitToLetters[1] = "";
            digitToLetters[2] = "abc";
            digitToLetters[3] = "def";
            digitToLetters[4] = "ghi";
            digitToLetters[5] = "jkl";
            digitToLetters[6] = "mno";
            digitToLetters[7] = "pqrs";
            digitToLetters[8] = "tuv";
            digitToLetters[9] = "wxyz";
            digitToLetters[0] = "";
            
            vector<string> stringLetters;
            
            for(auto c : digits)
            {
                int num = c - '0';
                
                string letters = digitToLetters.find(num)->second;
                // cout << "letters " << letters << endl;
                stringLetters.push_back(letters);
            }
            
            vector<string> output;
            queue<string> q;
            string letters = stringLetters[0];
            for(auto c : letters)
            {
                
                q.push(string(1,c));
            }
            int index = 1;
            
            while(!q.empty())
            {
                int size = q.size();
                
                for(int i = 0; i < size; i++)
                {
                    string s = q.front();
                    // cout << "s " << s << endl;
                    if(index < stringLetters.size())
                    {
                        string letters = stringLetters[index];
                        
                        for(auto c : letters)
                        {
                            q.push(s + c);
                            // cout << "s + c " << s + c << endl;
                        }
                    }
                    else
                    {
                        output.push_back(s);
                    }
                    
                    q.pop();
                }
                
                index++;
            }
            
            return output;
        }
    };

Log in to reply
 

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