问题可以分解为更小更简单的“子问题”,这些“子问题”可以进一步细分为更简单和更小的子问题。我们一个一个地取每一个数字并计算从任何数字可达的所有 ndigits,使用一个映射来存储从每个数字可达的数字的映射。当数字变为 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<string> output = new List<string>(); b.FindSequence("", "34", output); foreach (var item in output){ Console.WriteLine(item); } } } }输出结果
dg dh di eg eh ei fg fh fi