I use deep first search (DFS) idea. Is there any better solutions?


  • 4
    J

    Each path of DFS is a valid combination. We can solve the problem by enumerating every path.


  • 1
    S

    My solution is also DFS. I think the key point of this problem is find a way to enumerating all the possibilities. DFS and BFS are both ok.


  • 0
    A
    This post is deleted!

  • 0
    A

    How much time is it taking for you? My solution took 372 ms. I haven't used DFS or BFS.


  • 0
    J

    Mine is 12 ms


  • 0
    A

    Wow. Can you give me some hint about how to look at the problem as a DFS problem?


  • 0
    S

    @jarc, @atul4mlko, what language do you use? 12ms seems cpp. However, java can never be that fast.


  • 0
    A

    I used Java. I am not very comfortable with cpp. Also is there any way I can compare my timings with other users?


  • 1
    J

    Hi, mine is cpp. We can view it as a search problem. The search depth is the length of the input.


  • 0
    R

    I used BSF search and implemented it with recursion in C++. And my runtime was 4ms. The cost of time is quite related to the language we use but I don't think it means too much if we have similar time complexity.

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            unordered_map<char, string> phone_pad; //build hash table 
            phone_pad['2']= "abc";
            phone_pad['3']= "def";
            phone_pad['4']= "ghi";
            phone_pad['5']= "jkl";
            phone_pad['6']= "mno";
            phone_pad['7']= "pqrs";
            phone_pad['8']= "tuv";
            phone_pad['9']= "wxyz";
            
            vector<string> result;
            //string current = phone_pad[digits[0]];
            if (digits.size() == 0) { //in case the input is ""
            	result.push_back("");
            	return result;
            }
            string current = phone_pad[digits[0]];
            if (digits.size() == 1) { //close condition for recursion
            	for (int i = 0; i < current.size(); ++i) {
            		string tmp = "";
            		tmp.push_back(current[i]);
            		result.push_back(tmp);
            	}
            	return result;
            }
            string next = digits.substr(1, digits.size() - 1); 
            vector<string> iter = letterCombinations(next); //recursion for sub string and combine the result
            for (int i = 0; i < current.size(); ++i) {
            	for (int j = 0; j < iter.size(); ++j) {
            		string tmp = "";
            		tmp.push_back(current[i]);
            		result.push_back((tmp + iter[j]));
            	}
            }
            return result; 
        }
    };

  • 0
    Z

    o my god,4ms,...........

    25 / 25 test cases passed.
    Status: Accepted
    Runtime: 4 ms


  • 0
    U

    string current = phone_pad[digits[0]];
    This line is not good for the following reasons:

    1. if digits is empty, digits[0] will cause runtime error (index out of bound)
    2. if digits[0] is '1', which is not explicitly excluded from the input, phone_pad['1'] will also cause runtime error

  • 0
    R

    You are right. But in your second case, when digits[0] = '1', it will not cause runtime error because phone_pad is a map. But anyway, thanks for pointing that out. I will change my answer.


  • 0
    F

    can you share your answer ?


  • 18
    W

    in 4ms for 25/25

    class Solution {
    public:
    unordered_map<char, string> dig2char;
    Solution()
    {
        dig2char['2'] = "abc";
        dig2char['3'] = "def";
        dig2char['4'] = "ghi";
        dig2char['5'] = "jkl";
        dig2char['6'] = "mno";
        dig2char['7'] = "pqrs";
        dig2char['8'] = "tuv";
        dig2char['9'] = "wxyz";  
    }   
    
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if ( digits.size() == 0 )   
        {
            result.push_back("");
            return result;
        }       
        vector<string> temp = letterCombinations(digits.substr(1));
        for(int j = 0; j < dig2char[digits[0]].size(); j ++)
            for(int t = 0; t < temp.size(); t ++ )
                result.push_back(dig2char[digits[0]][j] + temp[t]);     
    
        return result;
    }
    

    };


  • 11
    D

    I think I got a brief solution, it is not recursive. But I believe it is BFS search. I think every solution should search all the paths. So your solution is good enough.
    Here is my solution:

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            //the s[n] means that the first letter of the button n is the (s[n])th letter in alphabet
            //eg. s[2] means that the first letter of the button 2 is the 0th letter in alphabet which is 'a'
            int s[]={0,0,0,3,6,9,12,15,19,22,26};
            //push an empty string, this may cause error if digits is empty :)
            vector<string> result(1);
            for(int i=0;i<digits.length();i++){
                vector<string> temp_vec;
                //for every string, append a new letter
                for(int j=0;j<result.size();j++){
                    int n=digits[i]-'1'+1;//get the button number
                    for(int k=s[n];k<s[n+1];k++) temp_vec.push_back(result[j]+char('a'+k));//append a new letter
                }
                result=temp_vec;
            }
            return result;
        }
    };
    

  • 6
    X

    Just an another solution that may inspire, with no recursion. Consider a string to be a large number with heterogenous base for each position, then just enumerate all of it, and do base conversion, also 4ms:

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            vector<string> ans;
            size_t m = 1, n = digits.size();
            for (auto &c: digits)
                m *= dict[c - '0'].length();
            for (size_t i = 0; i < m; i ++) {
                size_t p = i;
                string s = "";
                for (size_t j = 0; j < n; j ++) {
                    int c = digits[j] - '0';
                    int base = dict[c].length();
                    int v = p % base;
                    s += dict[c][v];
                    p /= base;
                }
                ans.push_back(s);
            }
            return ans;
        }
    };
    

  • 0
    P

    120ms in python, I think my solution is DFS-based as well.


  • 0
    H

    I think both DFS and Divide-and-Conque could solve this problem, but I don't think BFS is suitable for this problem.


  • 0
    X

    yes ,it's really bfs.in your solution you just enum you ret level by level,get the final ret in the finally loop


Log in to reply
 

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