LintCode 425. Letter Combinations of a Phone Number

很有意思的一道題。DFS經典使用
DFS几个要素:
1,写入最终结果的条件
2, 黑盒子什么功能
3, 带入黑盒子的参数。

class Solution {
public:
    /**
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    const vector<string> letters {"", "","abc","def", // '0','1','2',...
            "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  // 语法1
         
    vector<string> letterCombinations(string &digits) {
        // write your code here
        // DFS
        vector<string> res;
        int sizeD = digits.size();
        if(sizeD == 0){
            return res;
        }
        dfs(digits, res, 0, "");
        return res;
    }
    void dfs(string &digits, vector<string> &res, int cur, string path){
        if(cur == digits.size()){
            res.push_back(path);
            return;
        }
        for(auto elem : letters[digits[cur] - '0']){ //语法2
            dfs(digits, res, cur + 1, path + elem);
        }
    }
};

二刷2019年03月24日21:07:58
const vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> letterCombinations(string &digits) { // write your code here const int size = digits.size(); vector<string> res; if(size == 0){ return res; } string resElem; dfs(digits, res, resElem, 0); return res; } void dfs(string &digits, vector<string> &res, string resElem, int cur){ if(resElem.size() == digits.size()){ res.push_back(resElem); } for(int i = 0; i < mapping[digits[cur] - '0'].size(); i++){ dfs(digits, res, resElem + mapping[digits[cur] - '0'][i], cur + 1); } }

Comments

Popular posts from this blog

算法的比较

生命