Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

• Example:
  Input: “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.

解法——回溯

当一个题目，存在各种满足条件的组合，并且需要把它们全部列出来时，就要考虑回溯算法，但是回溯算法在一定程度上算是穷举，若数据较大不宜使用，可以考虑动态规划

public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<String>();
        if(digits.length()==0)
            return list;
        String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        letterCombinationsdfs(list,digits,"",0,map);
        return list;
    }

	private void letterCombinationsdfs(List<String> list, String digits, String res, int index, String[] map) {
		// TODO Auto-generated method stub
		if(index==digits.length())
		{
			list.add(res);
			return ;
		}
		String str=map[digits.charAt(index)-'0'];
		for(int i=0;i<str.length();i++)
		{
			letterCombinationsdfs(list, digits, res+str.charAt(i), index+1, map);
		}
	}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Letter Combinations of a Phone Number.
Memory Usage: 37.4 MB, less than 17.52% of Java online submissions for Letter Combinations of a Phone Number.

解法二——迭代

遍历digits 将第i个数字所代表的所有字母和list中之前保存的字母都加入tmp中 然后令list=tmp直到digits中所有数字都加完

public List<String> letterCombinations(String digits){
		 List<String> list=new ArrayList<String>();
	        if(digits.length()==0)
	            return list;
        list.add("");
	        String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	        for(int i=0;i<digits.length();i++)
	        {
	        	List<String> tmp=new ArrayList<String>();
	        	String str=map[digits.charAt(i)-'0'];
	        	for(int j=0;j<str.length();j++)
	        	{
	        		for(String s:list)
	        		{
	        			tmp.add(s+str.charAt(j));
	        		}
	        	}
	        	list=tmp;
	        }
	        return list;
	}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Letter Combinations of a Phone Number.
Memory Usage: 37.4 MB, less than 17.52% of Java online submissions for Letter Combinations of a Phone Number.