电话字母的组合

*
	 * 牛客网:回溯法
	 */
	ArrayList<String> res=new ArrayList<String>();
	public ArrayList<String> letterCombinations(String digits) {
		if(digits==null||digits.length()==0){
			res.add("");
			return res;
			
		}
		
		String[] mapping={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
		letterCombinations(digits,0,"",mapping);
		
		return res;
	}
	
	
	private void letterCombinations(String digits, int i, String string,String[] mapping) {
		if(i>=digits.length()){
			res.add(string);
			return;
		}
		String strs=mapping[Character.getNumericValue(digits.charAt(i))];
		
		for(char c:strs.toCharArray()){
			letterCombinations(digits,i+1,string+c,mapping);
		}
		
	}

class Solution {
private:
    map<char,string> mp={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string> res;
    string temp;
public:
    void combine(string &digits,int start){//回溯法
        if(start==digits.size()){
            res.push_back(temp);return;
        }
        for(int i=0;i<mp[digits[start]].size();i++){
            temp+=mp[digits[start]][i];
            combine(digits,start+1);
            temp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        combine(digits,0);
        return res;
    }
};

//dfs
public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        res.add("");
        if(digits ==null||digits.length()==0) return res;
        HashMap<Character,String> map =new HashMap<Character, String>();
        map.put('1',"1");
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        map.put('*',"*");
        map.put('0',"0");
        map.put('#',"#");
        return generate(res,digits,map);
    }
    public ArrayList<String> generate(ArrayList<String> res,String digits,HashMap<Character,String> map){
        if(digits ==null||digits.length()==0){
            return res;
        }
        ArrayList<String> list =new ArrayList<String>();
        for(int i=0;i<res.size();i++){
            String str =map.get(digits.charAt(0));
            for(int j=0;j<str.length();j++)
                list.add(res.get(i)+str.charAt(j));
        }
        res =new ArrayList<String>(list);
        list =generate(res, digits.substring(1),map);
        return list;
    }

class Solution {
public:
    string mp[12]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> letterCombinations(string digits) {
          vector<string> ans(1,"");
          for(int i=0;i<digits.size();i++){
              vector<string> tmp;
              for(int j=0;j<ans.size();j++)
              for(int k=0;k<mp[digits[i]-'0'].size();k++)
                  tmp.push_back(ans[j]+mp[digits[i]-'0'][k]);
              ans=tmp;
           }
          return ans;
    }
};

class Solution {
public:
   vector<string> letterCombinations(string digits) 
   {
    vector<string> res(1,"");
    int len = digits.size();
    if(len==0) return res;
    const string charMap[10] = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    for(int i=0;i<len;i++)
    {
      vector<string> temp;
      int num = digits[i]-'0';
      if(num<0 || num>9) break;
      string letter = charMap[num];
      for(int j=0;j<letter.length();j++)
      {
          for(int k=0;k<res.size();k++)
             temp.push_back(res[k]+letter[j]);
      }
      swap(res,temp);
    }
    sort(res.begin(),res.end());
    return res;
    }
};

枚举递归
class Solution {
public:
      vector<string> res;
    string tmp;
    map<int, string> num2alp = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9,"wxyz"}};
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            res.push_back(tmp);
            return res;
        }
        else
            getStr(digits, 0, tmp);
		return res;
        
    }
    void getStr(string digits, int idx, string tmp){
        if(idx == digits.size())
            res.push_back(tmp);
		int im = digits[idx] - '0';
        for(int i = 0; i < num2alp[im].size(); ++i){
            getStr(digits, idx + 1, tmp + num2alp[im][i]);
        }
    }
};

/**
  * 
  * @param digits string字符串 
  * @return string字符串一维数组
  */
function letterCombinations( digits ) {
    // write code here
    let phone = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    }
    let res = [];
    function backtrack(combination, next_digits){
        if(next_digits.length === 0){//如果数字串为空，则将当前字母组合插入到res
            res.push(combination);
        }
        else{
            for(let letter of phone[next_digits[0]]){//从数字串第一个数字开始循环处理
                backtrack(combination + letter, next_digits.substring(1));//将第一个数字的字母组合分别插入combination，再递归处理去掉首个数字剩下的数字串
            }
        }
    }
    if(digits){
        backtrack('', digits);//回溯函数入口
    }else{
        return [""];
    }
    return res;
}
module.exports = {
    letterCombinations : letterCombinations
};

class Solution:
    def letterCombinations(self , digits ):
        # write code here
        worddict = {'2':'abc','3':'def','4':'ghi','5':'jkl',
                    '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
        digits = list(digits)
        res = ['']
        for digit in digits:
            if digit in worddict:
                word = worddict[digit]
                l = len(word)
                n = len(res)
                #先对res扩容，再按顺序填充
                res = res*l
                for i in range(l):
                    for j in range(n):
                        res[i*n+j] = res[i*n+j] + word[i]
        return sorted(res)

    /*
    * 目的：给出所有可能的字母组合
    * 方法：回溯法
    */
    void solve(string digits, int pos, string cur, map<int,string>&m, vector<string>&res){
        if (pos== digits.size()){
            res.push_back(cur);
            return;
        }
        for (int i = 0; i<m[digits[pos]-'0'].size();++i){
            solve(digits,pos+1,cur+m[digits[pos]-'0'][i],m,res);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string>res;
        map<int,string>m;
        m[2]="abc";
        m[3]="def";
        m[4]="ghi";
        m[5]="jkl";
        m[6]="mno";
        m[7]="pqrs";
        m[8]="tuv";
        m[9]="wxyz";
        solve(digits, 0, "",m, res);
        return res;
    }

class Solution {
public:
    map<char,string> co={{'0',""},{'1',""},{'2',"abc"},{'3',"def"},{'4',"ghi"},
                         {'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string> out;
    void core(string s,string res,int idx,int l)
    {
        if(idx==l)
        {    
            out.push_back(res);
            return;
        }
        string s1=co[s[idx]];
        for(int i=0;i<s1.length();i++)
            core(s,res+s1[i],idx+1,l);
        if(s1.empty())
            core(s,res,idx+1,l);
    }
    vector<string> letterCombinations(string digits) 
    {
        out.clear();
        int l=digits.length();
        string res="";
        if(l>0)      
            core(digits,res,0,l);
        else
            out.push_back(res);
        return out;
    }
};

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string n2w[12] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> result(1,"");
        for(int i=0;i<digits.size();i++)
        {
        	vector<string> temp;
        	for(int j=0;j<result.size();j++)
        	{
        		int num = digits[i] - '0';
        		for(int k=0;k<n2w[num].size();k++)
        			temp.push_back(result[j]+n2w[num][k]);	        		
			}
			result = temp;
		}
		return result;
    }
};

回溯法：http://blog.csdn.net/versencoder/article/details/52071930
public class Solution {
    List<String> result=new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0)  return result;
        for(int i=0;i<digits.length();i++){
            if(digits.charAt(i)>'9'||digits.charAt(i)<'2')
                return result;
        }
        String[] str={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backtracking(str,digits,new StringBuilder(),0,digits.length());
        return result;
    }
    public void backtracking(String[] str,String digits,StringBuilder sb,int start,int k){
        if(k<0)    return ;
        else if(k==0)   {
            result.add(sb.toString());
            //sb=new StringBuilder();
        }
        else{
            for(int i=start;i<digits.length();i++){
                String s=str[digits.charAt(i)-50];
                for(int j=0;j<s.length();j++){
                    sb.append(s.charAt(j));
                    backtracking(str,digits,sb,i+1,k-1);
                    sb.deleteCharAt(sb.length()-1);
                }
            }
        }
    }
}

import java.util.*;


public class Solution {

     public String dicMap[]={"abc","def","ghi",
                             "jkl","mno","pqrs",
                             "tuv","wxyz"};
    
     public ArrayList<String> resultList=new ArrayList<String>();
     
    /* 
     * @param digits string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> letterCombinations (String digits) {
        // write code here
         char chArr[]=new char[digits.length()];
         place(0,chArr,digits);
         return resultList;
    }
    public void place(int index, char chArr[],String digits ){
        
        if(index==chArr.length){
            StringBuilder resultBuilder=new StringBuilder();
            for(int i=0;i<chArr.length;i++){
                resultBuilder.append(chArr[i]);
            }
            resultList.add(resultBuilder.toString());
        }else{
            Integer curDigit=digits.charAt(index)-'0';
            int curDigitIndex=curDigit-2;
            String allMayCharStr=dicMap[curDigitIndex];
            for(int i=0;i<allMayCharStr.length();i++){
                char ch=allMayCharStr.charAt(i);
                chArr[index]=ch;
                place(index+1,chArr,digits);
            }
           
        }     
    }
}
递归回溯法

class Solution: # 回溯
    def letterCombinations(self , digits):
        # write code here
        string = []
        allString = []
        pattern = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        length = len(digits)
        def combine(numIndex):
            if numIndex == length:
                allString.append("".join(string))
                return
            for s in pattern[digits[numIndex]]:
                string.append(s)
                combine(numIndex+1)
                string.pop()

        combine(0)
        return allString

Java版本的回溯解法。

    public ArrayList<String> letterCombinations (String digits) {
        // write code here
        traceBack(new StringBuffer(), 0, digits);
        return res;
    }


    // index为输入的数字字符串中的第几个数字
    private void traceBack(StringBuffer str, int index, String digits) {
        if (index == digits.length()) {
            res.add(str.toString());
            return;
        }
        char[] charArray = digits.toCharArray();
        // 目前回溯到第几个数字
        int num = Character.getNumericValue(charArray[index]);
        // 取出数字对应的字符串
        String item = mapping[num];
        for (char ch : item.toCharArray()) {
            str.append(ch);
            traceBack(str, index + 1, digits);
            str.deleteCharAt(str.length() - 1);
        }
    }