【Hot100】17. Letter combination of telephone number

17. Letter combination of telephone number

Reference resources ：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/

• to flash back
  Recursive calls are nested in the loop
  There is a small detail in the code implementation , If it is pure string splicing , Many temporary objects will be generated , The performance will be slightly worse ,Java In the implementation, we use StringBuilder Spliced , Tested time consuming 0 millisecond , If it is to use String It takes time for type splicing 6 millisecond .

class Solution {
    
	// A mapping table , The second position is "abc“, The third position is "def"...
	// It can also be used here map, Using arrays can save more memory 
	String[] letter_map = {
    " ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	public List<String> letterCombinations(String digits) {
    
		// Pay attention to the boundary conditions 
		if(digits==null || digits.length()==0) {
    
			return new ArrayList<>();
		}
		iterStr(digits, new StringBuilder(), 0);
		return res;
	}
	// The final output is list
	List<String> res = new ArrayList<>();
	
	// Recursive function 
	void iterStr(String str, StringBuilder letter, int index) {
    
		// The termination condition of recursion , Note that the termination conditions here look a little different from the dynamic demo , It is mainly optimized 
		// The dynamic graph is a part of each intercepted string ,"234", become "23", And then become "3", Finally become "", It doesn't perform well 
		// While using index Record the position of each traversal to the string , It's better 
		if(index == str.length()) {
    
			res.add(letter.toString());
			return;
		}
		// obtain index The character of position , Suppose the input character is "234"
		// The first time you recurs index by 0 therefore c=2, The second time index by 1 therefore c=3, third time c=4
		//subString Each time a new string is generated , and index Is to take the current character , So be more efficient 
		char c = str.charAt(index);
		//map_string The following table is from 0 Start all the way to 9, c-'0' You can get the relative array subscript position 
		// such as c=2 When ,2-'0', Get the subscript as 2,letter_map[2] Namely "abc"
		int pos = c - '0';
		String map_string = letter_map[pos];
		// Traversal string , For example, the first time I got 2, Page is traversal "abc"
		for(int i=0;i<map_string.length();i++) {
    
			// Call the next level of recursion , It is difficult to describe in words , Please understand with dynamic diagram 
            letter.append(map_string.charAt(i));
            // If it is String The splicing efficiency of type will be relatively low 
			//iterStr(str, letter+map_string.charAt(i), index+1);
            iterStr(str, letter, index+1);
            letter.deleteCharAt(letter.length()-1);
		}
	}
}

• queue
  You can take advantage of the first in, first out feature of queues , Then cooperate with the cycle

class Solution {
    
	public List<String> letterCombinations(String digits) {
    
		if(digits==null || digits.length()==0) {
    
			return new ArrayList<String>();
		}
		// A mapping table , The second position is "abc“, The third position is "def"...
		// It can also be used here map, Using arrays can save more memory 
		String[] letter_map = {
    
			" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
		};
		List<String> res = new ArrayList<>();
		// First, add a null character to the queue 
		res.add("");
		for(int i=0;i<digits.length();i++) {
    
			// Characters traversed by the current , Find the corresponding string in the dictionary table 
			String letters = letter_map[digits.charAt(i)-'0'];
			int size = res.size();
			// After calculating the queue length , Take out each element in the queue one by one 
			for(int j=0;j<size;j++) {
    
				// Take the first element out of the queue every time 
				String tmp = res.remove(0);
				// Then follow "def" Such string splicing , And put it in the queue again 
				for(int k=0;k<letters.length();k++) {
    
					res.add(tmp+letters.charAt(k));
				}
			}
		}
		return res;
	}
}