I don't think my BFS solution is good, although it turns out to be AC in 2ms. Any comment is welcomed!


  • 0
    W

    The main idea is BFS, and using a tail recursion to make the code more readable. Any different idea sharing is welcomed, including the improvement advice.

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> ret;
    		if (digits.length() == 0) {
    			string letters;
    			ret.push_back(letters);
    			return ret;
    		}
    		// Map between numbers and letters.
    		string tmp[] = {" ", "ΩΩ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    		vector<string> numToLetterMap(tmp, tmp + 10);
    		string letters;
    		letterCombinationsHelper(0, digits, numToLetterMap, letters, ret);
    		return ret;
    	}
    	void letterCombinationsHelper(const int &pos, const string &digits, const vector<string> &numToLetterMap, string letters, vector<string> &ret) {
    		if (pos >= digits.length()) {
    			ret.push_back(letters);
    			return;
    		}
    		for (int idx = 0; idx < numToLetterMap[digits[pos] - '0'].size(); ++idx) {
    			letterCombinationsHelper(pos + 1, digits, numToLetterMap, letters + numToLetterMap[digits[pos] - '0'][idx], ret);
    		}
    	}
    };

Log in to reply
 

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