LeetCode17. 电话号码的字母组合

题目描述

/**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     * 答案可以按 任意顺序 返回。
     * <p>
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     */

思路分析

1. 暴力解法如下
2. 优化解法
   • 递归 + 回溯

源码及分析

//思路分析
    //1. 编写一个根据字符串中数字获取响应字符的方法
    //2. 编写两个数字中字符组合的方法
    //3. 编写三个个数字中字符组合的方法
    //4. 编写四个数字中字符组合的方法
    public List<String> letterCombinations(String digits) {
        //字符串校验
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        if (digits.length() == 1) {
            String str = getStrByChar(digits.charAt(0));
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < str.length(); i++) {
                list.add(str.charAt(i) + "");
            }
            return list;
        }
        if (digits.length() == 2) {
            char c1 = digits.charAt(0);
            char c2 = digits.charAt(1);
            List<String> list = twoTetter(c1, c2);
            return list;
        }
        if (digits.length() == 3) {
            List<String> list = threeLetter(digits.charAt(0), digits.charAt(1), digits.charAt(2));
            return list;
        }
        if (digits.length() == 4) {

            List<String> list = fourLetter(digits.charAt(0), digits.charAt(1), digits.charAt(2), digits.charAt(3));
            return list;
        }
        return null;
    }

    //根据四个数字组合字符串的方法
    public List<String> fourLetter(char c1, char c2, char c3, char c4) {
        String str1 = getStrByChar(c1);
        String[] strings1 = str1.split("");
        String str2 = getStrByChar(c2);
        String[] strings2 = str2.split("");
        String str3 = getStrByChar(c3);
        String[] strings3 = str3.split("");
        String str5 = getStrByChar(c4);
        String[] strings5 = str5.split("");

        List<String> list = twoTetter(strings1, strings2);
        String[] strings4 = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            strings4[i] = list.get(i);
        }
        List<String> list2 = twoTetter(strings3, strings5);
        String[] strings6 = new String[list2.size()];
        for (int i = 0; i < list2.size(); i++) {
            strings6[i] = list2.get(i);
        }
        List<String> strings = twoTetter(strings4, strings6);
        return strings;
    }


    //根据三个数字组合字符串的方法
    public List<String> threeLetter(char c1, char c2, char c3) {
        String str1 = getStrByChar(c1);
        String[] strings1 = str1.split("");
        String str2 = getStrByChar(c2);
        String[] strings2 = str2.split("");
        String str3 = getStrByChar(c3);
        String[] strings3 = str3.split("");

        List<String> list = twoTetter(strings1, strings2);
        String[] strings4 = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            strings4[i] = list.get(i);
        }
        List<String> strings = twoTetter(strings4, strings3);
        return strings;
    }

    //根据两个字符串组合相应字符的方法
    public List<String> twoTetter(String[] str1, String[] str2) {
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < str1.length; i++) {
            for (int j = 0; j < str2.length; j++) {
                String str = str1[i] + str2[j];
                list.add(str);
            }
        }
        return list;
    }

    //根据两个数字组合相应字符的方法
    public List<String> twoTetter(char c1, char c2) {
        ArrayList<String> list = new ArrayList<>();
        String str1 = getStrByChar(c1);
        String str2 = getStrByChar(c2);

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                char[] ch = {str1.charAt(i), str2.charAt(j)};
                String s = new String(ch);
                list.add(s);
            }
        }
        return list;
    }

    //根据数字获取响应字符串的方法
    public String getStrByChar(char c) {
        String str = "";
        switch (c) {
            case '2':
                str = "abc";
                break;
            case '3':
                str = "def";
                break;
            case '4':
                str = "ghi";
                break;
            case '5':
                str = "jkl";
                break;
            case '6':
                str = "mno";
                break;
            case '7':
                str = "pqrs";
                break;
            case '8':
                str = "tuv";
                break;
            case '9':
                str = "wxyz";
                break;
        }
        return str;
    }