leetcode 17. Letter Combinations

17. 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.

解决方案：

使用递归解决问题：

在这个思路里面， 首先是将一个大问题变成一个数字的小问题，然后在此基础上每次加一个字，将这个数字所代表的代表每个都加在原来形成的字符串的上面

举例：
用户输入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<string> letterCombinations(string digits) {
        const string map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ans;
        if (digits.length() > 0) {
            // 先去掉第一位，变成一个规模小1的问题以递归解决
            vector<string> 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<string> letterCombinations(string digits)
    {
        if (digits.empty()) return {};
        //定义vector存储对应的点
        vector<vector<char>> 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<string> ans;
        dfs(digits, d, 0, cur, ans);
        return ans;
     } 
private:
    void dfs(const string& digits, const vector<vector<char>>& d, int l, string& cur, vector<string>& 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();
        }
    }
};

# 使用广度优先搜索

# 使用广度优先搜索
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<vector<char>> 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<string> ans{""};
        for (char digit : digits) {
            vector<string> tmp;
            for (const string& s : ans)
               for (char c : d[digit - '0'])
                    tmp.push_back(s + c);
            ans.swap(tmp);
        }
        return ans;
    }
};