Leetcode 17.电话号码的字母组合

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

示例:

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解题报告

典型的DFS。

• 设置一个索引index， 判断是否已经搜索到digits的末尾。
• 在 dfs() 内部，如果已经到digits末尾，将当前这条路生成的str添加到结果中。
• 如果还未到digits末尾，循环遍历下一步所能添加的字符，同时将索引index加1。

实现代码

class Solution{public:map<char, string> M = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};vector<string> letterCombinations(string digits){if(digits.size()==0) return {};vector<string>ans;dfs(ans, "", 0, digits);return ans;}// 这个地方的 ans必须是值引用void dfs(vector<string>&ans, string curStr, int index, string digits){if(index==digits.size()) ans.push_back(curStr);else{for(int i=0;i<M[digits[index]].size();i++){dfs(ans, curStr+M[digits[index]][i], index+1, digits);}}}
};

参考资料

[1] Leetcode 17. 电话号码的字母组合

Leetcode 22. 括号生成

问题描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题报告

类似于上一题，略。

实现代码

class Solution{public:vector<string> generateParenthesis(int n){if(n==0) return {};vector<string>ans;dfs(ans, "", n,0);return ans;}// 这个地方的 ans必须是值引用void dfs(vector<string>&ans, string target, int open, int close){if(open==0&&close==0) ans.push_back(target);else{if(open>0) dfs(ans, target+'(', open-1, close+1);if(close>0) dfs(ans, target+')', open, close-1);}}
};

参考资料

[1] Leetcode 22. 括号生成