Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
典型的dfs 或者说backtrace 思路
class Solution { map<char, string> m_maps; string m_digits; public: void backtrace(string & inStr, vector<string> & result) // void backtrace(string inStr, vector<string> & result) { if(inStr.size() == m_digits.size()) { result.push_back(inStr); return; } size_t inSize = inStr.size(); string charMap = m_maps[m_digits[inSize]]; for(size_t i = 0; i < charMap.size(); i++) { inStr += charMap[i]; backtrace(inStr, result); inStr.erase(inStr.end() - 1); } } vector<string> letterCombinations(string digits) { vector<string> result; string inStr; m_maps[‘2‘] = "abc"; m_maps[‘3‘] = "def"; m_maps[‘4‘] = "ghi"; m_maps[‘5‘] = "jkl"; m_maps[‘6‘] = "mno"; m_maps[‘7‘] = "pqrs"; m_maps[‘8‘] = "tuv"; m_maps[‘9‘] = "wxyz"; m_maps[‘0‘] = " "; m_digits = digits; backtrace(inStr, result); return result; } };
对于void backtrace(string & inStr, vector<string> & result) 和 void backtrace(string inStr, vector<string> & result) 都是正确的，有无引用都可以。
[LeetCode] Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/diegodu/p/4276573.html