17.电话号码的字母组合/回溯/队列【leetcode】-创新互联

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：
0<= digits.length<= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

该方法较好理解
如例子“23”
先将2对应的a，b，c加入队列，然后每次将a pop出队列时，将a分别与3对应的def分别组合加入队列。

代码如下：

class Solution {public:
    vectorletterCombinations(string digits) 
    {vectorres;
        string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        queueq;
        int n=digits.size();
        for(int i=0;iif(q.empty())
            {for(int j=0;jwhile(q.front().size()for(int j=0;jstring e=q.front()+s[digits[i]-'0'].substr(j,1);
                        q.push(e);
                    }
                    q.pop();
                }
            }
        }
        while(!q.empty())
        {res.push_back(q.front());
            q.pop();
        }
        return res;
    }
};

这个方法可能较为难理解
回溯其实可以理解为多条路分别走，你选择进入函数即走下一步，不进入函数往下走就是换个方向走，还没到下一步。
这里讲一讲回朔法的思路：1这一步要干嘛，2下一步要干嘛，3目的是什么
使用回溯法最好要能画成n叉树的结构，树的宽度就用for循环，深度就用递归。
另外回溯法要注意进入下一层递归时某些值才改变，可以在调用自身的括号中改变，不能在调用前面改变
如果不能在括号中改变，可以这样

for(int i=idx;iif(candidates[i]>target-sum) continue;
            if(candidates[i]<=target-sum)
            {v.push_back(candidates[i]);
                function(target,sum+candidates[i],candidates,v,i);
                v.pop_back();
            }
        }

push之后再pop这样就不会对后面for循环操作造成影响

另外，在同一层的回溯数据是不变的，但是二维数组传进去就可以积累答案，因为后面对一维数组有回溯操作，所以保证数据不变，而对结果数组没有，所以结果数组可以积累。
注意如果要可以积累的话，要传入地址！！！！！！！！！
int也是，如果传入的是固定的值，就可以不用传入地址。
然后这一题配一张图更好理解

首先第一步是把第一个数字的字符加进去，第二步是把第二个数字的字符加进去，目的是将字符相加并放入数组中
故可以用函数加字符，同时这里每一个数字都要回溯，故还有用for循环

class Solution {public:
    string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vectorres;
    void v(string digits,string ss,int idx)
    {   if(idx==digits.size()) res.push_back(ss);
       else
       {   string x=s[digits[idx]-'0'];
           for(int i=0;iletterCombinations(string digits) 
    {if(digits.size()==0) return res;
        v(digits,"",0);
        return res;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧