每一个数字对应了几个字母,把数字串转化为字母串,其实就是要去枚举
    image.png

    可以直接使用循环按照一个数字一个数字,去枚举字母,还可以利用dfs来枚举
    这里我使用map来存储,其实也可以使用其他数据结构来存储,例如
    map>, map, map>, vector 使用vector的时候能够使用下标来标识

    第一种:循环

    1. class Solution {
    2. vector<string> res;
    3. string _digits;
    4. unordered_map<int,string> mp;
    5. public:
    6. vector<string> letterCombinations(string digits) {
    7. if(digits == "") return vector<string>();
    8. _digits = digits;
    9. int idx = 0;
    10. mp.insert({0,"abc"});
    11. mp.insert({1,"def"});
    12. mp.insert({2,"ghi"});
    13. mp.insert({3,"jkl"});
    14. mp.insert({4,"mno"});
    15. mp.insert({5,"pqrs"});
    16. mp.insert({6,"tuv"});
    17. mp.insert({7,"wxyz"});
    18. vector<string> v1, v2;
    19. v1.push_back("");
    20. for(int i = 0; i < digits.size(); i++)
    21. {
    22. for(auto x: v1)
    23. {
    24. for(auto y: mp[digits[i] - '0' - 2])
    25. {
    26. string s = x+y;
    27. v2.push_back(s);
    28. }
    29. }
    30. v1 = v2;
    31. v2.clear();
    32. }
    33. return v1;
    34. }
    35. };

    第二种: dfs

    1. class Solution {
    2. vector<string> res;
    3. string _digits;
    4. unordered_map<int,string> mp;
    5. void dfs(int idx, string s)
    6. {
    7. if(idx == _digits.size())
    8. {
    9. res.push_back(s);
    10. return;
    11. }
    12. for(auto x: mp[_digits[idx] - '0' - 2])
    13. {
    14. string ns = s + x;
    15. dfs(idx+1, ns);
    16. }
    17. return;
    18. }
    19. public:
    20. vector<string> letterCombinations(string digits) {
    21. if(digits == "") return vector<string>();
    22. _digits = digits;
    23. int idx = 0;
    24. mp.insert({0,"abc"});
    25. mp.insert({1,"def"});
    26. mp.insert({2,"ghi"});
    27. mp.insert({3,"jkl"});
    28. mp.insert({4,"mno"});
    29. mp.insert({5,"pqrs"});
    30. mp.insert({6,"tuv"});
    31. mp.insert({7,"wxyz"});
    32. string s = "";
    33. dfs(idx, s);
    34. return res;
    35. }
    36. };
    1. class Solution {
    2. vector<string> res;
    3. vector<string> mp;
    4. void dfs(string digits, int idx, string path)
    5. {
    6. if(idx == digits.size())
    7. {
    8. res.push_back(path);
    9. return;
    10. }
    11. for(auto x: mp[digits[idx] - '0'])
    12. {
    13. dfs(digits, idx + 1, path + x);
    14. }
    15. }
    16. public:
    17. vector<string> letterCombinations(string digits) {
    18. if(!digits.size()) return res;
    19. mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    20. dfs(digits, 0,"");
    21. return res;
    22. }
    23. };

    第三种动态规划

    1. class Solution {
    2. public:
    3. vector<string> letterCombinations(string digits) {
    4. if(!digits.size()) return vector<string>();
    5. vector<string> mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    6. int n = digits.size();
    7. vector<vector<string>> f(n + 1);
    8. f[0].push_back("");
    9. for(int i = 1; i <= n; i++)
    10. {
    11. int val = digits[i - 1] - '0';
    12. for(auto x: f[i - 1])
    13. {
    14. for(auto y: mp[val])
    15. {
    16. f[i].push_back(x + y);
    17. }
    18. }
    19. }
    20. return f[n];
    21. }
    22. };

    第二次写题

    1. class Solution {
    2. public:
    3. vector<string> letterCombinations(string digits) {
    4. if(!digits.size()) return vector<string>();
    5. vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    6. vector<string> res = {""};
    7. for(auto d: digits)
    8. {
    9. int n = d - '0';
    10. vector<string> tmp;
    11. for(auto c: v[n])
    12. {
    13. for(auto s: res)
    14. {
    15. tmp.push_back(s + c);
    16. }
    17. }
    18. res = tmp;
    19. }
    20. return res;
    21. }
    22. };