侧边栏壁纸
  • 累计撰写 372 篇文章
  • 累计创建 60 个标签
  • 累计收到 109 条评论

目 录CONTENT

文章目录

LeetCode 第十七题 电话号码的字母组合

Z同学
2022-10-04 / 0 评论 / 1 点赞 / 68 阅读 / 1,152 字
温馨提示:
本文最后更新于 2022-10-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. 题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
image-1665554828334

就和我们手机的九宫格拼音一样。每个按键代表了多个字符情况。

例如:

  • 2:a,b,c
  • 3:d,e,f
  • 4:g,h,i
  • 5:j,k,l
  • 6:m,n,o
  • 7:p,q,r,s
  • 8:t,u,v
  • 9:w,x,y,z
  • 0:空格
示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:

输入:digits = ""
输出:[]
示例 3:

输入:digits = "2"
输出:["a","b","c"]

题目需要让我们给出组合情况值。

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

也就是最多输入长度为4,最少可以不输入。

2. 题解

当初想到的方法很简单,从用户输入的字符串中,提取每个字符,然后进行一个拼接成数组即可:

class Solution {
     public List<String> letterCombinations(String digits) {
        ArrayList<String> strings = new ArrayList<>();
        //得到字符
        int leng = digits.length();
        ArrayList<char[]> vector = new ArrayList<>();
        for (int i = 0; i < leng; ++i) {
            char[] s = numberToWord(digits.charAt(i));
            if (s != null) {
                vector.add(s);
            }
        }
        int charNum = vector.size();
        if (charNum == 0)
            return strings;
        char[] chars = vector.get(0);
        //得到第一项数组集合
        for (int i = 0; i < chars.length; ++i) {
            if (charNum == 1) {
                strings.add(chars[i] + "");
            } else if (charNum == 2) {
                xunhuan(1, strings, charNum, vector, chars[i] + "");
            } else {
                xunhuan(1, strings, charNum, vector, chars[i] + "");
            }
        }
        return strings;
    }

    public void xunhuan(int j, ArrayList<String> s, int max, ArrayList<char[]> vector, String fz) {
        //循环整个数组的长度
        for (char k : vector.get(j)) {
            if (j + 1 < max) {
                xunhuan(j + 1, s, max, vector, fz + k);
            } else {
                s.add(fz + k);
            }
        }
    }

    public char[] numberToWord(char digits) {
        switch (digits) {
            case '2':
                return new char[]{'a', 'b', 'c'};
            case '3':
                return new char[]{'d', 'e', 'f'};
            case '4':
                return new char[]{'g', 'h', 'i'};
            case '5':
                return new char[]{'j', 'k', 'l'};
            case '6':
                return new char[]{'m', 'n', 'o'};
            case '7':
                return new char[]{'p', 'q', 'r', 's'};
            case '8':
                return new char[]{'t', 'u', 'v'};
            case '9':
                return new char[]{'w', 'x', 'y', 'z'};
        }
        return null;
    }
}

执行用时: 6 ms

内存消耗: 41.8 MB

计算是得到了,但是效率明显不够高。找到了下面的这种算法。效率有了显著提升:

class Solution {
     public List<String> letterCombinations(String digits) {
          List<String> result = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return result;
        }
        String[] strs = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        //1.先算出一共有几种
        int len = 1;
        for(int i = 0; i < digits.length(); i++){
            int c = digits.charAt(i)-'0';
            len *= strs[c].length();
        }

//再用求余方法拿到每一种
        for(int i = 0 ; i < len; i++){
            int last = i;
            StringBuilder sb = new StringBuilder();
           for (int j=0; j< digits.length() ; ++j) {// 取字符值,每个循环就能拼接全部字数
                int c = digits.charAt(j) - '0';
                int pos = last % strs[c].length(); //取模得到当前字符的下标值
                sb.append(strs[c].charAt(pos)); // 拼接
                last = last / strs[c].length(); //循环开始第二个值
            }
            result.add(sb.toString());
        }
        return result;
      }
}

执行用时: 0 ms

内存消耗: 39.8 MB

效率方法明显提高了,整个代码量也减少了不少。 下面贴官方模板代码,

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, 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");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

官方使用的是回溯。效果也是一样的。

参考链接:

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/

1

评论区