【算法day16】电话号码的字母组合

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/submissions/613453566/

DFS"

class Solution {
public:vector<string> phone_string = {"abc", "def",  "ghi", "jkl","mno", "pqrs", "tuv", "wxyz"};string tmp;vector<string> ans;void DFS(int pos, string digits) {if (pos == digits.size()) {ans.push_back(tmp);return;}int num = digits[pos] - '0' - 2;for (int i = 0; i < phone_string[num].size(); i++) {tmp.push_back(phone_string[num][i]);DFS(pos + 1, digits);tmp.pop_back();}}vector<string> letterCombinations(string digits) {if (digits.size() == 0)return ans;DFS(0, digits);return ans;}
};

BFS

class Solution {
public:vector<string> phone_string = {"abc", "def",  "ghi", "jkl","mno", "pqrs", "tuv", "wxyz"};queue<string> q;vector<string> BFS(vector<string>& ch) {vector<string> ans;for (int i = 0; i < ch[0].size(); i++) {string str(1, ch[0][i]);q.push(str);}int j = 1;while (q.front().size() < ch.size()) {int len = q.size();for (int k = 0; k < len; k++) {string top = q.front();q.pop();for (int i = 0; i < ch[j].size(); i++) {q.push(top + ch[j][i]);}}j++;}for (; !q.empty(); q.pop()) {ans.push_back(q.front());}return ans;}vector<string> letterCombinations(string digits) {vector<string> ans;if (digits.size() == 0)return ans;vector<string> ch;for (int i = 0; i < digits.size(); i++) {ch.push_back(phone_string[digits[i] - '0' - 2]);}return BFS(ch);}
};