leetcode: 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.

原问题链接：https://leetcode.com/problems/letter-combinations-of-a-phone-number/

 

问题分析

   求给定数字对应的字符串组合,按照前面的示例,基本上是一个数字对应一个字符串。像数字1,对应的是空字符串,而数字0对应的是一个空格。因为是求一个给定数字串的组合。我们可以这样来考虑，对于若干个数字组成的串来说，首先取第一个数字，那么它就有它对应的那几个字符那几种组合。比如数字2对应的字符有"a", "b", "c" 3种。如果后面有多的字符的话，再取下一个，比如数字3，那么对应数字3的字符有“d”, "e", "f"。按照组合的关系，数字1和2对应的所有字符组合将有3乘以3= 9种。

    按照刚才的讨论，如果我们将每次组合后的结果保存起来，然后作为下一步组合拼接的起始集合，这样就可以得到若干个数字构成字符的所有组合。

    有了上述的讨论基础，我们来看怎么实现。首先一个就是要有每个数字所和所对应的字符串的关系。这里可以用一个数组来表示。数组的索引表示该数字，而对应的值表示映射的字符串。这种方式比较简单高效。在每次遍历digits里面的一个字符时，我们需要把这个字符对应的所有字符都加入到原有组合的每个元素里去。所以在这一步应该是一个二重循环，每次取一个对应的字符和原有的组合拼接起来，放到一个地方。然后再下一个，直到这几个字符组合遍历完。这些所有生成的新的结果将作为后面一个digits字符的构造基数。

    这样可以得到如下的代码：

 

public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] data = new String[] { " ", "", "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz" };
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < digits.length(); i++) {
            char[] c = data[digits.charAt(i) - '0'].toCharArray();
            List<String> temp = new ArrayList<String>();
            for (int j = 0; j < c.length; j++) {
                if (result.isEmpty()) result.add("");
                for (String s : result) temp.add(s + c[j]);
            }
            result = temp;
        }
        return result;
    }
}

    总的来说，这里是一个3重循环。因为每个字符对应的字符组合是固定的若干个。所以它的总体时间复杂度是在O()N * N)的范围。

 

总结

    这里的要点是要对数字和对应的元素建立好映射。同时要想到一个合理的办法将每次循环的结果都保存起来作为下一次的起始点。另外，在开始还要避免集合是空的情况。