leetcode17

问题描述：

Given a digit string, 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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

第一次看这道题还以为只是两个字符串中字符的笛卡尔积，但看到任意数字就知道了，这道题目像多个矩阵的乘积一样，需要先计算前面的字符串字符相加的结果，得到的结果再来和下一个字符串的字符进行笛卡尔积操作。最后得出结果。

这道题可以用一般方法来做，也可以做递归方法来。

首先一般方法:

1.初始化时将第一个字符串字符逐个加入list集合中，

2.取list集合中每一个元素与下一个字符串的每一个字符相加，加入集合list

3.去掉list集合中之前保存的字符串。如果处理的数字串字符没有处理完，则转2.否则结束

代码为:

public class Leetcode17 {
    private List<String> chas=new ArrayList<String>();
    private String []strs={" ","","abc","def","ghi","jkl","mn0","pqrs","tuv","wxyz"};
    public List<String> letterCombination(String digits){
        int len=digits.length();
        if(digits==null||digits.length()==0)
            return null;
        if(digits.length()==1){
            return Arrays.asList(digits.split(""));
        }
        
        
        
        int firstInt=Integer.parseInt(digits.charAt(0)+"");
        for(int i=0;i<strs[firstInt].length();i++){
            chas.add(strs[firstInt].charAt(i)+"");
        }
       
        for(int i=1;i<len;i++){
            int chaslen=chas.size();
            for(int j=0;j<chaslen;j++){
                int num=Integer.parseInt(digits.charAt(i)+"");
                String prev=chas.get(0);
                for(int k=0;k<strs[num].length();k++){
                
                String tmp=    prev+strs[num].charAt(k);
                chas.add(tmp);    
                }
                chas.remove(prev);
                
                
                
            }
            
            
            
            
            
            
            
        }
        return chas;
    }
    public static void main(String[] args) {
    
       List<String> list=new Leetcode17(). letterCombination("23");
        System.out.println(list);

    }
 
}

第二种方法是递归的方法：

   我们需要做的就是将之前计算的结果与下一个字符串的每一个字符相加，这是递归每一步都要做的，那么我们需要一个字符串a来保存之前计算的结果，还有变量i来计数递归的层数，每次递归完i+1，当i的长度为数字字符串的长度的时候，每一层数字字符对应的字母子串都已经处理完毕，则退出递归，

Java代码如下

	public void letterCombine(String digits,List<String> lists,String cur,int i){
		if(i==digits.length()){
			lists.add(cur);
			return ;
		}
		String str=strs[digits.charAt(i)-'0'];
		for(int j=0;j<str.length();j++){
			letterCombine(digits,lists,cur+str.charAt(j),i+1);
		}
		
		
		
	}