leetcode|leetcode 17. Letter Combinations of a Phone Number leetcode17.LetterCombinationsofaPhon

Letter Combinations of a Phone Number

Medium
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

leetcode|leetcode 17. Letter Combinations of a Phone Number

文章图片
image 解决方案：
使用递归解决问题：
在这个思路里面，首先是将一个大问题变成一个数字的小问题，然后在此基础上每次加一个字，将这个数字所代表的代表每个都加在原来形成的字符串的上面
举例：
用户输入23
2 a b c
3 d e f
首先，将其变成一个只含有3的问题
此时ans中只有 d e f
tmp <- ans
ans.push_back(map[digits[0] - '0'][i] + tmp[j]);
ad ae af
bd be bf
cd ce cf
结束

class Solution { public: vector letterCombinations(string digits) { const string map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector ans; if (digits.length() > 0) { // 先去掉第一位，变成一个规模小1的问题以递归解决 vector tmp = letterCombinations(digits.substr(1, digits.length() - 1)); // 处理边界情况 if (tmp.size() == 0) { tmp.push_back(""); } // 在递归计算出的答案前添加上所有第0位可能对应的字母来组成新的答案集 for (int i = 0; i < map[digits[0] - '0'].length(); i++) { for (int j = 0; j < tmp.size(); j++) { ans.push_back(map[digits[0] - '0'][i] + tmp[j]); } } } return ans; } };

# 使用深度优先搜索

class Solution { public: vector letterCombinations(string digits) { if (digits.empty()) return {}; //定义vector存储对应的点 vector> d(10); d[0] = {}; d[1] = {}; d[2] = {'a', 'b', 'c'}; d[3] = {'d', 'e', 'f'}; d[4] = {'g','h','i'}; d[5] = {'j','k','l'}; d[6] = {'m','n','o'}; d[7] = {'p','q','r','s'}; d[8] = {'t','u','v'}; d[9] = {'w', 'x', 'y', 'z'}; string cur; vector ans; dfs(digits, d, 0, cur, ans); return ans; } private: void dfs(const string& digits, const vector>& d, int l, string& cur, vector& ans) { if (l == digits.length()) { ans.push_back(cur); return ; } for (const char c: d[digits[l] - '0']) { cur.push_back(c); dfs(digits, d, l+1, cur, ans); cur.pop_back(); } } };

【leetcode|leetcode 17. Letter Combinations of a Phone Number】# 使用广度优先搜索

# 使用广度优先搜索 class Solution { public: vector letterCombinations(string digits) { if (digits.empty()) return {}; vector> d(10); d[0] = {' '}; d[1] = {}; d[2] = {'a','b','c'}; d[3] = {'d','e','f'}; d[4] = {'g','h','i'}; d[5] = {'j','k','l'}; d[6] = {'m','n','o'}; d[7] = {'p','q','r','s'}; d[8] = {'t','u','v'}; d[9] = {'w','x','y','z'}; vector ans{""}; for (char digit : digits) { vector tmp; for (const string& s : ans) for (char c : d[digit - '0']) tmp.push_back(s + c); ans.swap(tmp); } return ans; } };