Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Returns all possible letter combinations given a string containing only the numbers 2-9.”

Title link:

Source: LeetCode

Link: 17. Alphabetic combination of phone numbers – LeetCode (leetcode-cn.com)

2

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.

The mapping of numbers to letters is given as follows (same as a telephone key). 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"]Copy the code
Example 2: Input: digits = "2" Output: ["a","b"," C "]Copy the code

Second, the problem solving

1. Analysis of ideas

This problem can use a hash table to store all possible letters for each number, and then find all the solutions.

Take one digit at a time, enumerate all possible letters from the hash table, insert one of them after the existing letter, and continue to process the next digit until you run out of digits and end up with an array of letters.

When all combination words appear in the question, it is necessary to consider using the backtracking method, using the backtracking algorithm to find all feasible solutions, finding that one solution does not work, discarding the infeasible solution, enumerating all the solutions.

2. Code implementation

The combination of phone numbers is essentially a Cartesian product, written using LINq:

public class Solution {
    public IList<string> LetterCombinations(string digits) {
            IList<string> result = new List<string> ();if (string.IsNullOrEmpty(digits))
            {
                return result;
            }
            Dictionary<char.string> phoneDic = new Dictionary<char.string>() {
                {'2'."abc" },
                {'3'."def" },
                {'4'."ghi" },
                {'5'."jkl" },
                {'6'."mno" },
                {'7'."pqrs" },
                {'8'."tuv" },
                {'9'."wxyz"}};if (digits.Length == 1)
            {
                string temp = phoneDic[digits[0]].for (int i = 0; i < temp.Length; i++)
                {
                    result.Add(temp[i].ToString());
                }
                return result;
            }
            List<string> temps = new List<string> ();for(int i = 0; i < digits.Length; i++)
            {
                temps.Add(phoneDic[digits[i]]);
            }
            var tempResult = from m in temps[0]
                         from n in temps[1]
                         select new string("" + m + n);
            for(int i = 2; i < temps.Count; i++)
            {
                string temp = temps[i];
                tempResult = from m in tempResult
                             from n in temp
                             select new string("" + m + n);
            }
            result = tempResult.ToList();
            returnresult; }}Copy the code

3. Time complexity

Time complexity: O(N)

Space complexity: O(1)

Third, summary

Backtracking algorithms can be used to find all possible solutions.

When the word “find all combinations” appears in the question, you should think about whether backtracking algorithm can be used.

When using backtracking algorithm, if a solution is found to be infeasible, the infeasible solution is discarded.

In this case, because every letter for every number can be in a letter combination, there is no impossible solution, just enumerate all the solutions.