本文共 4204 字，大约阅读时间需要 14 分钟。

拨号键盘的字母组合问题

问题描述

给定一个数字串，返回这个数组串所表示的所有可能的字母组合。

例如：输入数字串“23”

注意：虽然上述答案在返回时是按照字典字母顺序排列的，但是你可以按照你想要的顺序返回结果。

算法设计

代码片段（一种求解算法）

public static List
   
     letterCombinations(String digits) {         List
    
      result =new ArrayList<>();         if(digits == null || digits.isEmpty())          return result;         result.add("");           String []btns = {
  "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};           for(int i =0 ; i < digits.length() ;i++)         {          List
     
       res = new ArrayList<>();          String letter = btns[digits.charAt(i)-'0'];          for(int j = 0 ; j < result.size();j++)//遍历上一个列表，取出每一个元素，并和新的元素的每一个字符加起来保存          {              for(int k = 0; k< letter.length(); k++)//遍历当前数字对应的所有字符              {                  res.add(result.get(j)+letter.charAt(k));              }          }          result = res;         }         return result;     }
     
    
   

下面再给出不同的求解算法

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.Iterator;import java.util.List;public class LetterCombinationsDemo2 {
       public static List
   
     letterCombinations(String digits) {        String digitletter[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };        List
    
      result = new ArrayList
     
      ();        if (digits.length() == 0)            return result;        result.add("");        for (int i = 0; i < digits.length(); i++)            result = combine(digitletter[digits.charAt(i) - '0'], result);        return result;    }    public static List
      
        combine(String digit, List
       
         l) {        List
        
          result = new ArrayList
         
          (); for (int i = 0; i < digit.length(); i++) for (String x : l) result.add(x + digit.charAt(i)); return result; } public static void main(String[] args) { // TODO Auto-generated method stub LetterCombinationsDemo2 lcd = new LetterCombinationsDemo2(); List
          
            list = lcd.letterCombinations("23"); Iterator
           
             itx = list.iterator(); while (itx.hasNext()) { String str = itx.next(); System.out.println(str); } }}
           
          
         
        
       
      
     
    
   

解法二：

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.Iterator;import java.util.List;public class LetterCombinationsDemo4 {    /*     * 算法设计分析     * 数字0-9对应的ASCII码值：依次为：48,49,50,51,52,53,54,55,56,57     * */    public List
   
     letterCombinations(String digits) {        List
    
      list = new ArrayList<>();        //        if (digits == null || digits.trim().length() == 0) return list;        String[] str = {
  "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};        //将字符串digits转化为字符数组，例如给定“23”，将转化为字符数组'2','3'        char[] ch = digits.trim().toCharArray();        int sum = 1;        String [] arr = new String[ch.length];        for (int i = 0; i < ch.length; i++) {           //从数组str中取出对应的字符串           // 例如 '2'-'0',得到结果 2，那么 str[2]则对应于"abc"; '3'-'0'，得到结果3,那么str[3]则对应于"def"           arr[i] = str[ch[i] - '0'];           System.out.print(arr[i]+"\t");        }        System.out.println();        list = new ArrayList<>(sum);        //调用组合方法，并返回处理结果       return  combination(arr, list, 0, "");    }    /*     * combination方法的作用     * 输入参数：     * String[] s     * List
     
       list     * int index     * String result     *      * */    private List
      
        combination(String[] s, List
       
         list, int index, String result) {        if (result.length() == s.length) {            list.add(result);            return list;        }        for (int i = index; i < s.length; i++) {            for (int j = 0; j < s[i].length(); j++) {                //递归调用，做笛卡尔积               combination(s,list, i + 1, result + s[i].substring(j, j + 1));            }        }        return list;     }    public static void main(String[] args) {        // TODO Auto-generated method stub        LetterCombinationsDemo4 lcd = new LetterCombinationsDemo4();        List
        
          list = lcd.letterCombinations("23"); Iterator
         
           itx = list.iterator(); while (itx.hasNext()) { String str = itx.next(); System.out.println(str); } }}
         
        
       
      
     
    
   

（完）