This is the 12th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

⚽ topic

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.

The sample1: Enter: digits ="23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"]
Copy the code

The sample2: Enter: digits =""Output: []Copy the code

The sample3: Enter: digits ="2"Output:"a"."b"."c"]
 
Copy the code

Tip:0 <= digits.length <= 4Digits [I] = range ['2'.'9']. Through the number of times313.172Submit the number548.644
Copy the code

⚽ A little thought

The length of the input string is less than or equal to 4. I don’t think there’s anything wrong with direct circulation. But now that we’re doing this problem, it’s definitely not going to be that straightforward. Let’s use a fancy sounding method called the su method, and what do we mean by su? Let’s just say recursion.

⚽ open dry

⚽ describes a function

We talked about HashMap and StringBuilder before and today we’re going to use StringBuffer() and we’re not going to use it exactly the same way as StringBuilder. Here are the key differences and distinctions

• Different: The principles and operations are basically the same, except that StringBufferd supports concurrent operations, is linearly safe, and is suitable for use in multiple threads. StringBuilder does not support concurrent operations, and is not safe for use in multiple threads. The newly introduced StringBuilder class is not thread-safe, but it performs better than StringBuffer in a single thread.
• Where it works: We should use the StringBuilder class first, without worrying about thread synchronization. If you want to be thread safe, StringBuffer.

⚽ source code and detailed

public class Solution {
	 public static void backtrack(List<String> combinations,Map<Character,String[]> map,String digits,StringBuffer combination,int index) {
		 if(digits.length()==index) {
			 combinations.add(combination.toString());
		 }else {
			 char d=digits.charAt(index);
			 String[] j=map.get(d);
			 //int jCount=j.length;
			 for(int i=0; i<j.length; i++) { combination.append(j[i]); backtrack(combinations, map, digits, combination, index+1); combination.deleteCharAt(index); }}}public static List<String> letterCombinations(String digits) {
		 List<String> combinations=new ArrayList<String>();
		 HashMap<Character,String[]> map=new HashMap<Character,String[]>() {{
		 
		 put('2'.new String[]{"a"."b"."c"});
         put('3'.new String[]{"d"."e"."f"});
         put('4'.new String[]{"g"."h"."i"});
         put('5'.new String[]{"j"."k"."l"});
         put('6'.new String[]{"m"."n"."o"});
         put('7'.new String[]{"p"."q"."r"."s"});
         put('8'.new String[]{"t"."u"."v"});
         put('9'.new String[]{"w"."x"."y"."z"});
		 }};
		 
		backtrack(combinations, map, digits, new StringBuffer(), 0);
		 return combinations;
		
	 }
	 public static void main(String[] args) {
		 System.out.println(letterCombinations("23")); }}Copy the code

I’m not going to say anything else because it’s pretty easy but I’m just going to talk about the backtracking part

// The first thing you need to understand is what the variable is for. This means that the map you used to store each digit ina shape is the one you used to store the letter to each digit
//digits is the input string. Combination is used to concatenate characters. Index is used to move the pointer to the input character
//2 or 3 or 4 is used
public static void backtrack(List<String> combinations,Map<Character,String[]> map,String digits,StringBuffer combination,int index) {
// To store the strings that meet the criteria into the final List
		 if(digits.length()==index) {
			 combinations.add(combination.toString());
		 }else {
			 char d=digits.charAt(index);// Get for example "234" is 2 or 3 or 4
			 String[] j=map.get(d);// Get an alphabetic array for each number
			 for(int i=0; i<j.length; i++) { combination.append(j[i]);// Used to concatenate characters
				 backtrack(combinations, map, digits, combination, index+1);/ / back
				 combination.deleteCharAt(index);/ / delete}}}Copy the code

Ok, so that’s the algorithm for today, and I’ll see you tomorrow.