# Letter Combinations of a Phone Number--LeetCode

xiaoxiao2021-02-28  12

### 1.题目

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.

### 3.分析

2）迭代版 依次读取数字 将数字可以代表的字符加入当前结果 然后进入下一次迭代 注意提前result.push_back(“”); string temp = result.front();不要写成string temp = result.begin(); 不要忘记return reuslt;

### 4.代码

1）递归版

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> result; if(digits.size() == 0) return result; string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; letterCombinationsDFS(result, dict, digits, 0, ""); return result; } void letterCombinationsDFS(vector<string> &result, string dict[], string digits, int level, string temp) { if(level == digits.size()) { result.push_back(temp); return; } string str = dict[digits[level] - '2']; for(int i = 0; i < str.size(); ++i) { temp.push_back(str[i]); letterCombinationsDFS(result, dict, digits, level + 1, temp); temp.pop_back(); } return; } };

2）迭代版

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> result; if(digits.size() == 0) return result; string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; result.push_back(""); for(int i = 0; i < digits.size(); ++i) { int n = result.size(); string str = dict[digits[i] - '2']; for(int j = 0; j < n; ++j) { string temp = result.front(); result.erase(result.begin()); for(int k = 0; k < str.size(); ++k) { result.push_back(temp + str[k]); } } } return result; } };