LeetCode17 Letter Combinations of a Phone Number

题意：

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.(Medium)

分析：

很好的练习搜索的题目，可以用BFS和回溯法（DFS）两种方式来做一下练习。

自己写的时候没太想明白回溯的写法（参数，返回值等等），写的是BFS的解法，DFS参考的讨论区。

代码1：

 class Solution {

 public:

     vector<string> letterCombinations(string digits) {

         string digMap[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

         vector<string> v;

         if (digits.size() == ) {

             return v;

         }

         queue<string> q;

         for (int i = ; i < digMap[digits[] - ''].size(); ++i) {

             q.push(string(,digMap[digits[] - ''][i] ));

         }

         for (int i = ; i < digits.size(); ++i) {

             int l = q.size();

             for (int j = ; j < l; ++j) {

                 string temp1 = q.front();

                 q.pop();

                 for (int k = ; k < digMap[digits[i] - ''].size(); ++k) {

                     string temp2 = temp1 + digMap[digits[i] - ''][k];

                     q.push(temp2);

                 }

             }

         }

         while (!q.empty()) {

             v.push_back(q.front());

             q.pop();

         }

         return v;

     }

 };

回溯法：

 class Solution {

 private:

     string digMap[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

     void dfs(vector<string>& v, string& tempStr, int index, string& digits) {

         if (index == digits.size()) {

             v.push_back(tempStr);

             return;

         }

         for (int i = ; i < digMap[digits[index] - ''].size(); ++i) {

             //tempStr += digMap[digits[index] - '0'][i];

             tempStr.push_back(digMap[digits[index] - ''][i]); //string的push_back和pop_back以前没用过

             dfs(v,tempStr,index + ,digits);

             tempStr.pop_back();

         }

     }

 public:

     vector<string> letterCombinations(string digits) {

         vector<string> result;

         if (digits.size() == ) {

             return result;

         }

         string tempStr;

         dfs(result,tempStr,,digits);

         return result;

     }

 };

巴特西

LeetCode17 Letter Combinations of a Phone Number

最新文章

热门文章