C++ first time to share my solution, hope can make friends here.


  • 0
    J
     class Solution {
     public:
        Solution(){
           s_numbers.clear();
           s_numbers[1] = "";
           s_numbers[2] = "abc";
           s_numbers[3] = "def";
           s_numbers[4] = "ghi";
           s_numbers[5] = "jkl";
           s_numbers[6] = "mno";
           s_numbers[7] = "pqrs";
           s_numbers[8] = "tuv";
           s_numbers[9] = "wxyz";
          }
       ~Solution()
       {
           s_numbers.clear();
       }
       vector<string> letterCombinations(string digits)
       {
           vector<string> outStrings;
           if (!digits.empty())
             connectLetters(digits, string(""), outStrings);
           return outStrings;
       }
     private:
         bool connectLetters(string digits, const string& prefixStr, vector<string>& outStrings)
         {
           if( digits.empty())     {
               outStrings.push_back(prefixStr);
           return true;
           }
           int connectNumber = digits[0] - '0';
           map<int,string>::iterator numerIt = s_numbers.find(connectNumber);
           if( numerIt == s_numbers.end())   {
              return false;
           }
           string connectString = numerIt->second;
           digits.erase(0,1);
    
           for( size_t i = 0; i < connectString.size(); i++ )   {
               string newPrefix = prefixStr + connectString[i];
               connectLetters(digits, newPrefix, outStrings);
           }
           return true;
         }
       private:
           map<int,string> s_numbers;
     };

  • 0
    J
    This post is deleted!

  • 1

    @JellyH Dude, you're really making this complicated. Check this solution of mine.

    class Solution {
    private:
        int Len;
        string digit_map[8]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        void search(const string& digits, int pos, string path, vector<string>& v)
        {
            if(pos == Len) return ;
            string s = digit_map[digits[pos]-'2'];
            for(int i = 0; s[i]; ++i)
            {
                if(pos == Len-1) v.push_back(path+s[i]);
                else search(digits, pos+1, path+s[i], v);
            }
        }
    public:
        vector<string> letterCombinations(string digits) 
        {
            Len = digits.length();
            vector<string> v;
            search(digits, 0, "", v);
            return v;
        }
    };
    

  • 0

    Or this

    class Solution {
    private:
        int Len;
        string digit_map[8]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        void search(const string& digits, int pos, string path, vector<string>& v)
        {
            if(pos == Len) { v.push_back(path); return ; }
            string s = digit_map[digits[pos]-'2'];
            for(int i = 0; s[i]; ++i)
                search(digits, pos+1, path+s[i], v);
        }
    public:
        vector<string> letterCombinations(string digits) 
        {
            Len = digits.length();
            vector<string> v;
            if(!Len) return v;
            search(digits, 0, "", v);
            return v;
        }
    };
    

  • 0
    J

    @LHearen hi brother, thanks a lot for your reply, I read your code very carefully, you are right ! your solution looks more simple. compare your solution, I think our solution is similar. the difference is : first you use array to keep the strings and I use std::map, the second you use 'int' to record the pos and I use string and direct erase the number witch I have dealt it to record the pos. I can do some change to let them looks more similar. BTW, how to post code as C++ style like yours.

    class Solution {
     public:
        vector<string> letterCombinations(string digits)
        {
            vector<string> outStrings;
            if (!digits.empty())
                connectLetters(digits, string(""), outStrings);
            return outStrings;
        }
     private:
        bool connectLetters(string digits, const string& prefixStr, vector<string>& outStrings)
        {
            if( digits.empty()) {
                outStrings.push_back(prefixStr);
                return true;
            }
            string connectString = s_numbers[digits[0] - '0'];
            if( connectString.empty()) return false;
            digits.erase(0,1);
            for( size_t i = 0; i < connectString.size(); i++ )   {
                string newPrefix = prefixStr + connectString[i];
                connectLetters(digits, newPrefix, outStrings);
            }
            return true;
        }
        map<int,string> s_numbers = {{1,""},{2,"abc"},{3,"def"},{4,"ghi"},{5,"jkl"},{6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"}};
    };
    

  • 0

    @JellyH You are really bad at formatting your code, man... using three backquotes for code block using single backquotes for code line.


  • 0
    J

    @LHearen many thanks buddy!!! forgive me, it's my first time to use this. I have no idea about how to formatting my code block.


  • 0

    @JellyH ``` is the three backquotes Okay, I do it for you this time.


  • 0

    @JellyH Your solution now looks for more clean, still you can achieve better. Good luck, man.


  • 0
    J

    @LHearen it works! so much thank you! you are so amazing! XD XD


  • 0
    J

    @LHearen thanks buddy! good luck to you! you make my day! nice to chat with you!


  • 0

    @JellyH Sure thing, man. We're Leetcoders, we are brothers.


  • 0
    S

    @LHearen My code runs really slow it took 8ms, can you please help me improve this.

    class Solution {
    public:
    	vector<string> s;
    	void recurse(string digits, unordered_map<char, vector<char>> maps, int digit, int letter, string st) {
    		if (st.length() == digits.length()) {
    			s.push_back(st);
    			return;
    		}
    		if (digit > digits.size())
    			return;
    		if (letter > maps[digits[digit]].size())
    			return;
    
    		for(int i=0;i<maps[digits[digit]].size();i++)
    				recurse(digits, maps, digit+1, i, st + char(maps[digits[digit]][i]));
    	}
    	vector<string> letterCombinations(string digits) {
    	    if(!digits.length())
    	        return s;
    		unordered_map<char, vector<char>> maps;
    		maps['2'] = vector<char>{ 'a','b','c' };
    		maps['3'] = vector<char>{ 'd','e','f' };
    		maps['4'] = vector<char>{ 'g','h','i' };
    		maps['5'] = vector<char>{ 'j','k','l' };
    		maps['6'] = vector<char>{ 'm','n','o' };
    		maps['7'] = vector<char>{ 'p','q','r','s' };
    		maps['8'] = vector<char>{ 't','u','v' };
    		maps['9'] = vector<char>{ 'w','x','y','z' };
    		
    		recurse(digits, maps, 0, 0, "");
    		return s;
    	}
    };
    

  • 0

    @sujiths52 try to use char *ss[] to replace maps<char, vector<char>>


  • 0
    S

    @LHearen I declared and initialized maps globally and it took 0ms.
    Anyways, thank you.


  • 0
    S

    @LHearen Can you please tell me how to use char*ss[]? I am not very comfortable with pointers.


  • 0

    @sujiths52 Check this post of mine, in C++ actually you can just adopt string.

    Sometimes the OJ will fluctuate in time cost, your solution using map is definitely not as efficient as array to index.


Log in to reply
 

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