วิธีหาการจัดหมู่ทั้งหมดของคีย์พาดโทรศัพท์มือถือโดยใช้ Backtracking ด้วย C#

ปัญหานี้สามารถแบ่งเป็น "โจทย์ย่อย" ที่เล็กลงและง่ายขึ้น ซึ่งสามารถแบ่งต่อไปได้อีก เราเอาแต่ละหลักมาทีละหลักและนับตัวเลข n หลักที่เข้าถึงได้จากหลักใดหลักหนึ่ง ใช้ map เพื่อเก็บการแมปของตัวเลขที่เข้าถึงได้จากทุกหลัก เมื่อตัวเลขกลายเป็น n หลัก ให้อัปเดตจำนวน

ตัวอย่าง

using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
    public class BackTracking
    {
        private string GetKeyPadValueBasedOnInput(string digit)
        {
            Dictionary keypad = new Dictionary();
            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 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 output = new List();
            b.FindSequence("", "34", output);
            foreach (var item in output)
            {
                Console.WriteLine(item);
            }
        }
    }
}

ผลลัพธ์

dg dh di eg eh ei fg fh fi