首页 > itarticle > 17. letter combinations of a phone number(medium) 解法一（mine）解法二（官方）解法三

17. letter combinations of a phone number(medium) 解法一（mine）解法二（官方）解法三

admin 11月 24, 2020 0

原题

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

原题翻译

描述：
给定包含2-9（包含2和9）的数字的字符串，返回该数字可能表示的所有可能的字母组合。

题目描述

例如：

输入： “23”

输出： [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

另外：

虽然上述例子的输出是按字典顺序排列的，但您的答案可以是任何顺序。

解法一（mine）

主要思想

使用String数组保存字符串和数字映射关系（只需数组下标+2，即可获取对应数字）。
获得输入字符串中所有数字对应的字符串，存入集合（letterList）。
取出letterList中第一个元素，分割成字符数组，分别放入集合1（res1）。
取出letterList中第二个元素，分割成字符数组，与集合1中的所有元素进行乘积运算，将结果分别放入集合2（res2）。
res1和res2交换，以保证需要进行乘积运算的集合为res1。
重复步骤3和4，直至遍历完letterList。
最后一步无需再交换res1和res2，直接返回res2即可。

运行速度：超过了65.32%的解答。

内存使用：超过了98.63%的解答。

源码

class  {
      public List<String> letterCombinations(String digits) {
        
        String[] letters = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        char[] charArray = digits.toCharArray();
        // 保存digits每个字符对应的string集合
        List<String> letterList = new LinkedList<>();
        for (char c : charArray) {
            // 注意：这里需要char转int，若直接(int)c，会返回ascII码
            letterList.add(letters[Integer.parseInt(String.valueOf(c)) - 2]);
        }
        List<String> res1 = new LinkedList<>();
        List<String> res2 = new LinkedList<>();
        List<String> temp;
        for (String letter : letterList) {
            char[] chars = letter.toCharArray();
            if (res2.size() == 0) {
                // 若res2为空，直接将letter放入即可
                for (char c : chars) {
                    res2.add(String.valueOf(c));
                }
            } else {
                // 若res2不为空，交换res1和res2
                temp = res1;
                res1 = res2;
                res2 = temp;
                // 将遍历letter中每个字符，分别拼接res1中的每一个字符串，并放入res2
                for (char c : chars) {
                    for (String s : res1) {
                        res2.add(s + c);
                    }
                }
                // 清空res1
                res1.clear();
            }
        }
        return res2;
    }
}

解法二（官方）

主要思想

使用map存储（比解法一中的直接数组下标进行存取，更方便维护）。
回溯。

运行速度：超过了65.32%的解答。

内存使用：超过了98.63%的解答。

源码

class  {
    Map<String, String> phone = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
    }};
    List<String> output = new ArrayList<String>();

    public void backtrack(String combination, String next_digits) {
        // if there is no more digits to check
        if (next_digits.length() == 0) {
            // the combination is done
            output.add(combination);
        }
        // if there are still digits to check
        else {
            // iterate over all letters which map
            // the next available digit
            String digit = next_digits.substring(0, 1);
            String letters = phone.get(digit);
            for (int i = 0; i < letters.length(); i++) {
                String letter = phone.get(digit).substring(i, i + 1);
                // append the current letter to the combination
                // and proceed to the next digits
                backtrack(combination + letter, next_digits.substring(1));
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0)
            backtrack("", digits);
        return output;
    }
}

解法三

主要思想

讨论区的答案，与官方答案类似。

注意几点优化的操作：

使用StringBuilder优化String的拼接。
arr[c - '0']的写法，比解法一中的arr[Integer.parseInt(String.valueOf(c))]更间接有效，
LinkedList比ArrayList更快地增删元素。

运行速度：超过了100%的解答。

内存使用：超过了98.63%的解答。

源码

class  {
    String arr[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new LinkedList<String>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0) {
            recurse(new StringBuilder(), digits, 0);
        }
        return res;
    }

    private void recurse(StringBuilder sb, String digits, int pos) {
        char c = digits.charAt(pos);
        String curr = arr[c - '0'];
        for (int i = 0; i < curr.length(); i++) {
            c = curr.charAt(i);
            sb.append(c);
            if (pos == digits.length() - 1) {
                res.add(sb.toString());
            } else {
                recurse(sb, digits, pos + 1);
            }
            sb = sb.deleteCharAt(sb.length() - 1);
        }
    }
}