LeetCode 17：Letter Combinations of a Phone Number

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：像电话号码一样，按了几个键，每个键上的字符都要出现在结果里，我理解成了不论按了多少键，都是两个字符之间的组合

2：顺序问题，按键有先后次序，因此对应的字符组合也有先后次序，比如23，那么只能ad，不能da

因此一开始我的做法就先根据数字字符串获取每个数字对应的按键字符串，存放在ArrayList里，数字有序，我也是依次add的，然后遍历输出组合，外层循环i从0开始，内层循环从i+1开始，保证次序以及不重复；然后ArrayList里也要遍历字符串每个字符，抠出来拼成String，存放在myList里，最终return

当然这个已经是意思理解错之后的错误答案了

package com.maoxiaomeng;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    public List<String> letterCombinations(String digits) {
        //  2      3      5
        //a b c  d e f  j k l
        String[] strs = {"", "abc", "def", "ghi", "jkl",
                "mno", "pqrs", "tuv", "wxyz"};

        List<String> myList = new ArrayList<String>();
        if (digits.length() == 0) {
            return myList;
        } else if (digits.length() == 1) {
            for (String a : strs[Integer.valueOf(digits) - 1].split("")) {
                myList.add(a);
            }
            return myList;
        }

        List<String> tempList = new ArrayList<String>();
        for (int i = 0; i < digits.length(); i++) {
            int index = digits.charAt(i) - '0';
            tempList.add(strs[index - 1]);
        }

        for (int i = 0; i < tempList.size(); i++) {
            for (int j = i + 1; j < tempList.size(); j++) {
                for (int k = 0; k < tempList.get(i).length(); k++) {
                    for (int m = 0; m < tempList.get(j).length(); m++) {
                        String myStr = String.valueOf(tempList.get(i).charAt(k)) +
                                String.valueOf(tempList.get(j).charAt(m));
                        myList.add(myStr);
                    }
                }
            }
        }

        return myList;
    }
}

既然没法确认到底数字字符串的长度是多少，就没法这么简单地遍历了，不可能无数个循环，就只有递归了

package com.maoxiaomeng;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    public List<String> letterCombinations(String digits) {

        String[] strs = {"", "abc", "def", "ghi", "jkl",
                "mno", "pqrs", "tuv", "wxyz"};
        List<String> myList = new ArrayList<String>();
        recursiveCombinations(myList, digits, "", 0, strs);

        return myList;
    }
    
    public void recursiveCombinations(List<String> myList, String digits, 
                                      String current, int index, String[] strs) {
        if (index == digits.length()) {
            if (current.length() != 0) {
                myList.add(current);
            }
            return;
        }
        /**
         *  2      3      5
         *a b c  d e f  j k l
         *index = 0, myStr = "abc", current = "", next = "a"
         *recursiveCombinations(myList, "235", "a", 1, strs)
         *index = 1, myStr = "def", current = "a", next = "a" + "d"/"e"/"f"
         *recursiveCombinations(myList, "235", "ad"/"ae"/"af", 2, strs)
         *index = 2, myStr = "jkl", current = "ad"/"ae"/"af", next = current + "j"/"k"/"l"
         * ......
         */
        String myStr = strs[digits.charAt(index) - '0' - 1];
        for (int i = 0; i < myStr.length(); i++) {
            String next = current + myStr.charAt(i);
            
            recursiveCombinations(myList, digits, next, index + 1, strs);
        }
    }
}

参考了下Solution，大半夜的，想着头大