Bài toán có thể được chia thành các "bài toán con" nhỏ hơn và đơn giản, có thể được chia nhỏ hơn nữa thành các bài toán con đơn giản hơn và nhỏ hơn. Chúng tôi lấy từng chữ số một và đếm tất cả các chữ số có thể đạt được từ bất kỳ chữ số nào, sử dụng bản đồ để lưu trữ ánh xạ các chữ số có thể đạt được từ mỗi chữ số. Khi chữ số trở thành chữ số n, hãy cập nhật số lượng.
Ví dụ
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<string> output = new List<string>();
b.FindSequence("", "34", output);
foreach (var item in output){
Console.WriteLine(item);
}
}
}
} Đầu ra
dg dh di eg eh ei fg fh fi