首页 > 代码库 > 【LeetCode】Letter Combinations of a Phone Number
【LeetCode】Letter Combinations of a Phone Number
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.
枚举所有情况。
对于每一个输入数字，对于已有的排列中每一个字符串，分别加入该数字所代表的每一个字符。
所有是三重for循环。
举例：
初始化排列{""}
1、输入2，代表"abc"
已有排列中只有字符串""，所以得到{"a","b","c"}
2、输入3，代表"def"
(1)对于排列中的字符串"a"，分别加入‘d‘,‘e‘,‘f‘，得到{"b","c","ad","ae","af"}
(2)对于排列中的字符串"b"，分别加入‘d‘,‘e‘,‘f‘，得到{"c","ad","ae","af","bd","be","bf"}
(2)对于排列中的字符串"c"，分别加入‘d‘,‘e‘,‘f‘，得到{"ad","ae","af","bd","be","bf","cd","ce","cf"}
class Solution {public: map<char, string> m; void buildMap() { m[‘0‘] = " "; m[‘1‘] = "0"; m[‘2‘] = "abc"; m[‘3‘] = "def"; m[‘4‘] = "ghi"; m[‘5‘] = "jkl"; m[‘6‘] = "mno"; m[‘7‘] = "pqrs"; m[‘8‘] = "tuv"; m[‘9‘] = "wxyz"; } vector<string> letterCombinations(string digits) { vector<string> result; if(digits == "") { result.push_back(""); return result; } buildMap(); queue<string> q; q.push(""); for(int i = 0; i < digits.size(); i ++) {//for each digit string curStr = m[digits[i]]; //append every char in curStr to each string already in q int size = q.size(); for(int j = 0; j < size; j ++) { string last = q.front(); q.pop(); //for each letter a digit may represent for(int k = 0; k < curStr.size(); k ++) { char curC = curStr[k]; string temp = last + curC; //last not changed q.push(temp); } } } while(!q.empty()) { string str = q.front(); result.push_back(str); q.pop(); } return result; }};
【LeetCode】Letter Combinations of a Phone Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。