Leetcode系列（1）

一、 电话号码的字母组合

leetcode第17题：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。

 

示例:

输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路：利用BFS的思想逐层向下搜索，遍历给定字符串中的结果。

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if(digits.length()==0) { return res; } res.push_back(""); map<char,string> findTable={ {'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"}, {'8',"tuv"},{'9',"wxyz"} }; for(int i=0;i<digits.length();++i) { vector<string> temp; for(char tab:findTable[digits[i]]) { for(int j=0;j<res.size();++j) { temp.push_back(res[j]+tab); } } res=temp; } return res; } };

二、括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

思路：先用左括号，然后使用右括号和左括号匹配。

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; if (n == 0 || n<0) { return res; } calcSum(n, n, "", res); return res; } void calcSum(int left, int right, string str, vector<string> &bRes) { if (right == 0||left>right) { return; } if (left == 0) { string tStr = str; for (int i = 0; i<right; ++i) { tStr += ")"; } bRes.push_back(tStr); return; } str += "("; calcSum(left - 1, right, str, bRes); str[str.length() - 1] = ')'; calcSum(left, right - 1, str, bRes); } };