Accepted c++ solution use backtracking, 0ms, very easy understand


  • 0

    The follow is my accepted c++ solution use backtracking. Does not require much explanation, it is easy to understand.

    class Solution {
    public:
    	Solution() {
    		dict.push_back("");
    		dict.push_back("");
    		dict.push_back("abc");
    		dict.push_back("def");
    		dict.push_back("ghi");
    		dict.push_back("jkl");
    		dict.push_back("mno");
    		dict.push_back("pqrs");
    		dict.push_back("tuv");
    		dict.push_back("wxyz");
    	}
        std::vector<std::string> letterCombinations(std::string digits) {
    		std::vector<std::string> res;
    		std::string combinations = "";
    		letterCombinations(digits, res, combinations, 0);
    		return res;
        }
    private:
    	std::vector<std::string> dict;
    	void letterCombinations(std::string &digits, std::vector<std::string> &res, std::string combinations, int pos) {
    		if (pos == digits.size() && !combinations.empty()) {
    			res.push_back(combinations);
    			return;
    		}
    		std::string letters = dict[digits[pos] - '0'];
    		++pos;
    		if (letters.empty()) {
    			letterCombinations(digits, res, combinations, pos);
    			return;
    		}
    		for (std::string::iterator iter = letters.begin(); iter != letters.end(); ++iter)
    			letterCombinations(digits, res, combinations + *iter, pos);
    	}
    };

Log in to reply
 

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