This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging
On August 8, China finished the Tokyo Olympics with 88 MEDALS. Although the final moment of the gold medal tally was overtaken by the United States, but it is a satisfactory ending. Finally differ this gold medal, may let the table tennis mixed doubles project lose the gold medal more diaphragm should. Sometimes life is like this. Although I have prepared well and tried my best, some external factors beyond my control may lead to another direction
The Flag I set yesterday is still standing today. I went out to exercise for a long time. Let’s continue to work hard in the next few days.
Let’s continue with problem 17 of Leetcode today. It’s not difficult, but it’s interesting to see a new solution.
The title
Given a string containing only the numbers 2-9, return all the combinations of letters it can represent. The answers can be returned in any order.
Give the mapping of numbers to letters as follows (same as telephone keys). Note that 1 does not correspond to any letter.
Example 1: input: who = “23” output: [” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”]
Example 2: Input: digits = “” Output: []
Example 3: Input: digits = “2” Output: [“a”,”b”,”c”]
Train of thought
Yeah, the easiest way to think about it is to just go through it, and for every number, there might be three or four letters, and just enumerate it. But since the length of the number is uncertain, we can’t just write for, we can write recursively. I don’t think it’s going to tell you anything, it’s just going to show you how to write this recursion, and introduce you to another way of thinking about it. Given a numeric string, you can think of it as an N-digit number, but instead of a decimal number, it is a decimal number (7 and 9 can represent four letters), and each digit represents the number of the optional letter (starting from the 0th). In this case, we can compute all the possibilities, M, and then we can go through 0 M minus 1, which is 0 M minus 1, k, and we can translate k to this n digit, so that every one of them has a unique letter. The trick here is, when you translate k to this n number, you translate from the lowest order, so you end up reversing the whole string. 2 -> ABC 3 possibilities 7 -> PQRS 4 possibilities 5 -> JKL 3 possibilities so the total number of possibilities = 3 * 4 * 3 = 36 Traversal 0~35: The 0 possibility is translated into 3 number 000 and the corresponding string is apj. The 1 possibility is translated into 3 number 001 and the corresponding string is APK. The 2 possibility is translated into 3 number 002 and the corresponding string is APL. The 3 possibility is translated into 3 number 010 and the corresponding string is aqj… Possibility 12 translates to 3 for 100, and the corresponding string is BPJ… The 35th possibility translates to 3 for 232, and the corresponding string is CSL
Java version code
class Solution { public List<String> letterCombinations(String digits) { Map<Character, String> map = new HashMap<>(); map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); List<String> ans = new ArrayList<>(); int len = digits.length(); if (len == 0) { return ans; } // Total number of possible cases int count = 1; for (int i = 0; i < len; i++) { char digChar = digits.charAt(i); String letters = map.get(digChar); count *= letters.length(); } for (int index = 0; int index = 0; index < count; index++) { StringBuilder item = new StringBuilder(); int lastNum = index; For (int j = len-1; int j = len-1; j >=0; j--) { char digChar = digits.charAt(j); String letters = map.get(digChar); int lettersLen = letters.length(); item.append(letters.charAt(lastNum % lettersLen)); lastNum /= lettersLen; } // Add (item.reverse().toString()); } return ans; }}Copy the code