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.
Although the above answer is in lexicographical order, your answer could be in any order you want.
分析
方法一
每个字母都会独自展开一个分支,就是排列组合问题。DFS搜索
/| /| /|"425"|g h i 4
a b c a b c a b c 7
.
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public : vector<string> alphabets = { "" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" }; vector<string> letterCombinations(string digits) { int len = digits.size(); vector<string> result; if ( len == 0) return result; dfs(digits, 0, "" , result); return result; } void dfs(string digits, int pos, string path, vector<string> & result){ if (digits.size() == pos){ result.push_back(path); return ; } for (auto d: alphabets[digits[pos] - '0' ]){ dfs(digits, pos + 1, path + d, result); } } }; |
方法二
可以先将0...1的所有排列找到-->{"a", "b", "c"}
再进一步将0...2的所有排列找到-->{"ad", "ae","af", "bd", "be", "bf", "cd", "ce", "cf"}
如此循环...直到字符串末尾。实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public : vector<string> charmap = { "" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" }; vector<string> letterCombinations(string digits) { vector<string> res; if (digits.size() == 0) return res; res.push_back( "" ); for ( int i = 0; i < digits.size(); i++) { vector<string> tempres; string chars = charmap[digits[i] - '0' ]; for ( int c = 0; c < chars.size();c++) for ( int j = 0; j < res.size();j++) tempres.push_back(res[j]+chars[c]); res = tempres; //重新赋值结果vector数组 } return res; } }; |