队列法

package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class demo_17 {
    public List<String> letterCombinations(String digits) {
        List<String> li =new ArrayList<String>();
        HashMap<Character, String> hm=new HashMap<Character, String>();
        Queue<String> q=new LinkedList<String>();
        if(digits=="") {return li;}
        hm.put('2', "abc");
        hm.put('3',"def" );
        hm.put('4',"ghi" );
        hm.put('5',"jkl" );
        hm.put('6',"mno" );
        hm.put('7',"pqrs" );
        hm.put('8',"tuv" );
        hm.put('9',"wxyz" );
        //现将第一个数字对应的字符串各个字符入队列
        for(int j=0;j<hm.get(digits.charAt(0)).length();j++) {
            q.offer(String.valueOf(hm.get(digits.charAt(0)).charAt(j)));
        }
        for(int i=1;i<digits.length();i++) {
            String s=hm.get(digits.charAt(i));
            //记录原先队列的长度，方便控制循环次数
            int length=q.size();
            for(int j=0;j<length;j++) {
                //保留当前出队的字符串
                String ss=q.poll();
                for(int k=0;k<s.length();k++) {
                    q.offer(ss+s.charAt(k));
                }
            }
        }
        for(String s:q) {
            li.add(s);
        }
        System.out.println(li);
        return li;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_17 d17 =new demo_17();
        d17.letterCombinations("23");
    }

}

回溯法

https://blog.csdn.net/weiyuefei/article/details/79316653