首页 > 代码库 > [LeetCode] Letter Combinations of a Phone Number（bfs）
[LeetCode] Letter Combinations of a Phone Number（bfs）
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.
用queue实现bfs：
class Solution {public: map<char,string> m; vector<string> letterCombinations(string digits) { vector<string> result; m[‘2‘]="abc"; m[‘3‘]="def"; m[‘4‘]="ghi"; m[‘5‘]="jkl"; m[‘6‘]="mno"; m[‘7‘]="pqrs"; m[‘8‘]="tuv"; m[‘9‘]="wxyz"; queue<string> q; string s; q.push(s); result = bfs(q,digits); return result; } vector<string> bfs(queue<string> q,string &digits){ vector<string> result; int len = digits.size(); if(len==0){ string s; result.push_back(s); return result; } while(!q.empty()){ string s = q.front(); int n = s.size(); q.pop(); if(n==len){ result.push_back(s); continue; } string s0(s); char c = digits[n]; int alphaNum = m[c].size(); for(int i =0;i<alphaNum;i++){ s.push_back(m[c][i]); q.push(s); s = s0; } } return result; }};
[LeetCode] Letter Combinations of a Phone Number（bfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。