Cách lấy tất cả tổ hợp giá trị bàn phím di động bằng backtracking C#

Vấn đề có thể chia thành các "bài toán con" nhỏ hơn đơn giản, tiếp tục chia nhỏ hơn nữa. Chúng ta lấy từng chữ số một và đếm tất cả các chữ số n-digit có thể đạt được từ chữ số đó, dùng map để lưu ánh xạ các chữ số đạt được từ mỗi chữ số. Khi chữ số trở thành n-digit, cập nhật đếm.

Ví dụ

using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
    public class BackTracking
    {
        private string GetKeyPadValueBasedOnInput(string digit)
        {
            Dictionary<string, string> keypad = new Dictionary<string, string>();
            keypad.Add("2", "abc");
            keypad.Add("3", "def");
            keypad.Add("4", "ghi");
            keypad.Add("5", "jkl");
            keypad.Add("6", "mno");
            keypad.Add("7", "pqrs");
            keypad.Add("8", "tuv");
            keypad.Add("9", "wxyz");
            return keypad.GetValueOrDefault(digit);
        }

        public void FindSequence(string currentList, string digits, List<string> output)
        {
            if (digits.Length == 0)
            {
                output.Add(currentList);
                return;
            }
            else
            {
                string digit = digits.Substring(0, 1);
                string letters = GetKeyPadValueBasedOnInput(digit);
                for (int i = 0; i < letters.Length; i++)
                {
                    char letter = GetCHarFromString(letters, i);
                    FindSequence(currentList + letter, digits.Substring(1), output);
                }
            }
        }

        private char GetCHarFromString(string letters, int value)
        {
            char[] charArr = letters.ToCharArray();
            return charArr[value];
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            List<string> output = new List<string>();
            b.FindSequence("", "34", output);
            foreach (var item in output)
            {
                Console.WriteLine(item);
            }
        }
    }
}

Kết quả

dg dh di eg eh ei fg fh fi

Giải thích: Sinh tất cả tổ hợp chữ cái từ chuỗi số "34" trên bàn phím điện thoại cũ. Số 3 ↔ def, số 4 ↔ ghi. Kết quả 9 tổ hợp: dg, dh, di, eg, eh, ei, fg, fh, fi.