[Backtracking interview questions] facebook interview questions - letter combinations of phone numbers (two solutions)

content

Topic description

Backtracking solution

Solve using queues

Topic description

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

Given a string containing only the numbers 2-9, return all letter combinations it can represent. The mapping of numbers to letters is given as follows (same as phone keys). Note that 1 does not correspond to any letter.

Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
illustrate:
Although the answers above are in lexicographical order, you are free to choose the order in which the answers are output.

Backtracking solution

The solution to this problem is to use backtracking, which sets recursive calls in the loop. Originally recursion is not easy to understand, coupled with the recursion of the loop, it is even more difficult to understand.
Let's not consider recursion first, let's see how to solve the following problem.
Assuming that the input is 2 and there is only one character, how should it be solved?
According to the title requirement 2 = "abc", so the result should be ["a","b","c"]
Don't think about how to write recursion first, just think about how to print the result.
This is too simple, a loop will do it:

result = List()
for(i=0;i<len("abc");i++) {
    tmp = i
    result.add(tmp)
}
return result

The above is pseudo code, a loop will do it.

If the input is 23, what should I do? The result of 23 is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"], we still don't think about how to write recursion , just thinking about how to get this result out. code show as below:

result = List()
for(i=0;i<len("abc");i++) {
    for(j=0;j<len("def");j++)
        tmp = i+j
        result.add(tmp)
}
return result

That is to say, a string of length 2 such as 23 can be handled with two layers of loops.
If the input is 234, still don't think about how to write recursion, but how to print the result.

result = List()
for(i=0;i<len("abc");i+=1) {
    for(j=0;j<len("def");j+=1) {
        for(k=0;k<len("ghi");k+=1) {
            tmp = i+j+k
            result.add(tmp)
        }
    }
}
return result

This time, three layers of loops were used.
If the input is 2345, then the code can be written like this:

result = List()
for(i=0;i<len("abc");i+=1) {
    for(j=0;j<len("def");j+=1) {
        for(k=0;k<len("ghi");k+=1) {
            for(n=0;n<len("jkl");n+=1)
                tmp = i+j+k+n
                result.add(tmp)
        }
    }
}
return result

This time, four layers of loops were used. Can you see some doorway now? correct. The number of nested levels of the loop is the length of the input string. The input string length is 1, and the loop has only 1 layer.
The length of the input string is 3, and the loop is 3 layers. If the input string length is 10, then the loop is 10 layers.
However, the length of the input string is not fixed, and the number of nested levels of the corresponding loop is not fixed. How to solve this situation? This is where recursion comes in handy.

For printing a string like "2345":
The first recursion is the bottom square in the above figure, and after processing the first character 2, change the input character to "345" and call the second recursive function
The second recursive process 3, change the string to "45" and recurse again
The third recursive processing 4, change the string to "5" and continue the recursion
The fourth recursive processing 5, change the string to "" and continue the recursion
Finally found that the string is empty, put the result in the list and return
The above is from the point of view of function call, and every time the next layer of recursion is called, some processing results of this layer need to be put into a temporary variable, and then passed to the next layer, and passed from this variable layer by layer The time complexity of this algorithm is very high, it is at the level of O(3^n), and the space complexity is O(n)

The dynamic diagram is as follows:

 

java code implementation:

class Solution {
	//A mapping table with "abc" in the second position and "def" in the third position. . .
	//map can also be used here, and arrays can save some memory.
	String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	public List<String> letterCombinations(String digits) {
		//Pay attention to boundary conditions
		if(digits==null || digits.length()==0) {
			return new ArrayList<>();
		}
		iterStr(digits, "", 0);
		return res;
	}
	//list of final output results
	List<String> res = new ArrayList<>();
	
	//recursive function
	void iterStr(String str, String letter, int index) {
		//Recursive termination condition, note that the termination condition here looks a little different from the dynamic demo diagram, mainly due to some optimizations
		//The dynamic picture is a part of the string that is intercepted each time, "234", becomes "23", then becomes "3", and finally becomes "", so the performance is not good
		//And use index to record the position of each traversal to the string, so the performance is better
		if(index == str.length()) {
			res.add(letter);
			return;
		}
		//Get the character at the index position, assuming the input character is "234"
		//In the first recursion, the index is 0 so c=2, the second index is 1 so c=3, and the third time c=4
		//subString will generate a new string every time, and index is to take the current character, so it is more efficient
		char c = str.charAt(index);
		//The following table of map_string is from 0 to 9, c-'0' can get the relative array subscript position
		//For example, when c=2, 2-'0', get the subscript as 2,letter_map[2] is "abc"
		int pos = c - '0';
		String map_string = letter_map[pos];
		//Traverse the string, for example, the first time you get 2, the page is to traverse "abc"
		for(int i=0;i<map_string.length();i++) {
			//Calling the next layer of recursion is difficult to describe in words, please understand it with dynamic diagrams
			iterStr(str, letter+map_string.charAt(i), index+1);
		}
	}
}

python code implementation:

class Solution(object):
	def letterCombinations(self, digits):
		"""
		:type digits: str
		:rtype: List[str]
		"""
		# Pay attention to boundary conditions
		if not digits:
			return []
		# A mapping table with "abc" in the second position and "def" in the third position. . .
		# map can also be used here, and arrays can save some memory.
		d = [" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
		# list of final output results
		res = []
		
		# recursive function
		def dfs(tmp,index):
			# Recursive termination condition, note that the termination condition here looks a little different from the dynamic demo diagram, mainly due to some optimizations
			# The dynamic picture is a part of the string that is intercepted each time, "234", becomes "23", then becomes "3", and finally becomes "", so the performance is not good
			# And use index to record the position of each traversal to the string, so the performance is better
			if index==len(digits):
				res.append(tmp)
				return
			# Get the character at the index position, assuming the input character is "234"
			# In the first recursion, the index is 0 so c=2, the second index is 1 so c=3, and the third time c=4
			# subString will generate a new string every time, and index is to take the current character, so it is more efficient
			c = digits[index]
			# The following table of map_string is from 0 to 9, ord(c)-48 is the ASCII code to get c and then -48,48 is the ASCII code of 0
			# For example, when c=2, 2-'0', the subscript is 2, and letter_map[2] is "abc"
			letters = d[ord(c)-48]
			
			# Traverse the string, for example, the first time you get 2, the page is to traverse "abc"
			for i in letters:
				# Calling the next layer of recursion is difficult to describe in words, please understand it with dynamic diagrams
				dfs(tmp+i,index+1)
		dfs("",0)
		return res

Solve using queues

We can use the first-in, first-out feature of the queue, and then cooperate with the cycle to complete the problem requirements.
We first put the characters "a","b","c" corresponding to 2 into the queue in turn

Then take the first element "a" from the queue, and splicing it with the characters "d","e","f" corresponding to 3 one by one

So the queue becomes like this:

In the same way, "b" is taken out of the queue, and then spliced ​​with the characters "d", "e", and "f" corresponding to 3, and the queue becomes as follows:

The dynamic demonstration is as follows:

 

java code implementation:

class Solution {
	public List<String> letterCombinations(String digits) {
		if(digits==null || digits.length()==0) {
			return new ArrayList<String>();
		}
		//A mapping table with "abc" in the second position and "def" in the third position. . .
		//map can also be used here, and arrays can save some memory.
		String[] letter_map = {
			" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
		};
		List<String> res = new ArrayList<>();
		//Add a null character to the queue first
		res.add("");
		for(int i=0;i<digits.length();i++) {
			//From the current traversed character, take the dictionary table to find the corresponding string
			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 from the queue each time
				String tmp = res.remove(0);
				//Then concatenate with a string like "def" and put it in the queue again
				for(int k=0;k<letters.length();k++) {
					res.add(tmp+letters.charAt(k));
				}
			}
		}
		return res;
	}
}

python code implementation:

class Solution(object):
	def letterCombinations(self, digits):
		"""
		:type digits: str
		:rtype: List[str]
		"""	
		if not digits:
			return []
		# A mapping table with "abc" in the second position and "def" in the third position. . .
		# map can also be used here, and arrays can save some memory.
		d = [" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
		# Add a null character to the queue first
		res = [""]
		for i in digits:
			size = len(res)
			# From the current traversed character, take the dictionary table to find the corresponding string
			letters = d[ord(i)-48]
			# After calculating the queue length, take out each element in the queue one by one
			for _ in xrange(size):
				# Take the first element from the queue each time
				tmp = res.pop(0)
				# Then concatenate with a string like "def" and put it in the queue again
				for j in letters:
					res.append(tmp+j)
		return res

Welcome to scan and pay attention to the public number, there are more graphic algorithm interview questions waiting for you~

Tags: Python Algorithm leetcode queue string

Posted by johnpaine on Sat, 07 May 2022 10:12:49 +0300