c# - 尝试用递归更优雅地解决电话词

Question

我已经查看了 Stack Overflow，但仍然无法正常工作。如果我错过了一个明显的帖子，我深表歉意。

我有一个学校问题涉及获取电话号码，获取所有可能的单词组合，然后将其写入文本文件。我做到了，并为我的任务获得了全部荣誉。我能够用七个嵌套循环来做到这一点，但这不是很优雅而且非常死板。当我发现教科书的解决方案是七个嵌套循环时，我感到非常震惊和失望。我的导师也没有任何答案。

我已经尝试了很多不同的方法，但我一直无法拨入它。我确定了一个递归和终止点，但从未能够让它工作。我可以生成字母序列，但与应有的数量相去甚远。我注释掉了我的尝试，这样你就可以看到我失败的思维过程:)请看看，如果你有任何想法，请告诉我。

public partial class TelephoneWorderizer : Form
{
    protected Dictionary<int, IEnumerable<string>> KeyMappings = new Dictionary<int, IEnumerable<string>>();
    protected string[][] ActiveLettersGroups = null;
    protected List<string> Words = new List<string>();
    protected List<string> RecursiveWords = new List<string>();
    protected int Iteration = 0;

    public TelephoneWorderizer()
    {
        InitializeComponent();

        this.KeyMappings = this.GetKeyMappings();
    }

    private void btnGetWords_Click(object sender, EventArgs e)
    {
        string textBoxContent = textBoxNumber.Text;

        int[] digits = this.GetPhoneNumbers(textBoxContent);

        List<string> words = this.GetWords(digits);

        using (StreamWriter writer = new StreamWriter(@"E:\words.txt"))
        {
            foreach (var word in words)
            {
                writer.WriteLine(word);
            }
        }

        textBoxNumber.Clear();
    }

    private List<string> GetWords(int[] digits)
    {
        List<string[]> letterGroupings = new List<string[]>();

        //digits array of numbers
        for (int i = 0, j = digits.Length; i < j; i++)
        {
            int digit = digits[i];

            //if the number has a letter group mapped to it
            if (this.KeyMappings.ContainsKey(digit))
            {
                // letters mapped to a given number
                letterGroupings.Add(this.KeyMappings[digit].ToArray());
            }
        }

        this.WordMakerLoop(letterGroupings);
        //this.WordMaker(letterGroupings);

        return this.Words;
        //return this.RecursiveWords;
    }

    //private void RecursionTest(string word, List<string[]> groups, int letterCtr, int groupCtr)
    //{
    //    string[] Group = groups[groupCtr];

    //    word += Group[letterCtr];

    //    letterCtr += 1;

    //    if (letterCtr < Group.Length - 1)
    //    {
    //        letterCtr = 0;
    //        groupCtr += 1;

    //        // Hit bottom
    //        if (groupCtr == groups.Count - 1)
    //        {
    //            groupCtr -= 1;
    //        }

    //        RecursionTest(word, groups, letterCtr, groupCtr);
    //    }
    //}

    private void WordMaker(List<string[]> letterCollections)
    {
        string newword = "";
        int numberLength = letterCollections.Count;

        this.ActiveLettersGroups = letterCollections.ToArray();

        string[] letterGroup = this.ActiveLettersGroups[0];

        this.RecursiveGetWords(newword, 0, 0);
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="word"></param>
    /// <param name="groupIndex"></param>
    /// <param name="letterIndex"></param>
    private void RecursiveGetWords(string word, int groupIndex, int letterIndex)
    {

        /*
         * 
         * 
         * 
         */


        var numActiveLetterGroups = this.ActiveLettersGroups.Length;

        if (this.ActiveLettersGroups.Length > 0 && this.Iteration < numActiveLetterGroups)
        {
            if (groupIndex < numActiveLetterGroups)
            {
                var letters = this.ActiveLettersGroups[groupIndex]; // Picks the a letter group ex: A, B, C 

                if (letterIndex < letters.Length)
                {
                    //var letter1 = letters.Select(x => 
                    string letter = letters[letterIndex]; // Picks a letter from the group ex: A

                    word += letter;

                    this.RecursiveGetWords(word, groupIndex + 1, this.Iteration);
                }
                else
                {
                    //this.RecursiveWords.Add(word);
                    //word = "";

                    //this.RecursiveGetWords(word, 0, 1);
                }
            }
            else
            {
                this.RecursiveWords.Add(word);
                word = "";
                this.Iteration++;

                this.RecursiveGetWords(word, 0, this.Iteration);
            }
        }
    }

    #region
    private void WordMakerLoop(List<string[]> letterGroups)
    {
        string word = "";

        // array of string[]
        var newGroup = letterGroups.ToArray();

        //grabs a letter group
        for (int i = 0; i < newGroup.Length; i++)
        {
            var letterGroup1 = newGroup[i];

            //grabs a letter from group 1
            for (int j = 0; j < letterGroup1.Length; j++)
            {
                string letter1 = letterGroup1[j];

                if (i + 1 < newGroup.Length)
                {
                    var letterGroup2 = newGroup[i + 1];

                    //grabs a letter from group 2
                    for (int k = 0; k < letterGroup2.Length; k++)
                    {
                        string letter2 = letterGroup2[k];

                        if (i + 2 < newGroup.Length)
                        {
                            var letterGroup3 = newGroup[i + 2];

                            //grabs a letter from group 3
                            for (int l = 0; l < letterGroup3.Length; l++)
                            {
                                string letter3 = letterGroup3[l];

                                if (i + 3 < newGroup.Length)
                                {
                                    var letterGroup4 = newGroup[i + 3];

                                    //grabs a letter from group 4
                                    for (int m = 0; m < letterGroup4.Length; m++)
                                    {
                                        string letter4 = letterGroup4[m];

                                        if (i + 4 < newGroup.Length)
                                        {
                                            var letterGroup5 = newGroup[i + 4];

                                            //grabs a letter from group 5
                                            for (int n = 0; n < letterGroup5.Length; n++)
                                            {
                                                string letter5 = letterGroup5[n];

                                                if (i + 5 < newGroup.Length)
                                                {
                                                    var letterGroup6 = newGroup[i + 5];

                                                    //grabs a letter from group 6
                                                    for (int o = 0; o < letterGroup6.Length; o++)
                                                    {
                                                        string letter6 = letterGroup6[o];

                                                        if (i + 6 < newGroup.Length)
                                                        {
                                                            var letterGroup7 = newGroup[i + 6];

                                                            //grabs a letter from group 6
                                                            for (int p = 0; p < letterGroup7.Length; p++)
                                                            {
                                                                string letter7 = letterGroup7[p];

                                                                word = letter1 + letter2 + letter3 + letter4 + letter5 + letter6 + letter7;
                                                                this.Words.Add(word);
                                                                word = "";
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // Sanitizes input text and converts the string into and arra of int
    private int[] GetPhoneNumbers(string content)
    {
        int[] phoneNumbers = null;

        string cleanString = this.SanitizeString(content);

        int numbers;

        if (Int32.TryParse(cleanString, out numbers))
        {
            //phoneNumbers = this.GetIntArray(numbers).OfType<int>().ToList();
            phoneNumbers = this.GetIntArray(numbers);
        }

        return phoneNumbers;
    }

    // Removes potential unwanted characters from the phone number
    private string SanitizeString(string content)
    {
        content = content.Replace("-", "");
        content = content.Replace("(", "");
        content = content.Replace(")", "");

        return content;
    }

    //breaks a number into an array of its individual digits
    private int[] GetIntArray(int num)
    {
        List<int> listOfInts = new List<int>();

        while (num > 0)
        {
            listOfInts.Add(num % 10);
            num = num / 10;
        }

        listOfInts.Reverse();

        return listOfInts.ToArray();
    }

    //gets the mappings for the numerical values
    private Dictionary<int, IEnumerable<string>> GetKeyMappings()
    {
        List<string> alphabet = new List<string>() { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
        Dictionary<int, IEnumerable<string>> mappings = new Dictionary<int, IEnumerable<string>>();

        for (int i = 0; i < 10; i++)
        {
            string[] letters = null;
            switch (i)
            {
                case 0:
                case 1:
                    break;
                case 2:
                case 3:
                case 4:
                case 5:
                case 6:
                case 8:
                    letters = alphabet.Take(3).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 3);
                    break;
                case 7:
                case 9:
                    letters = alphabet.Take(4).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 4);
                    break;
                default:
                    break;
            }
        }

        return mappings;
    }
    #endregion
}

让我强调一下，对于那些有疑问的人，学校作业已经结束了。我想做得更好，更有效率。如果有帮助，我可以将我的项目发布到 gitHub 上。

Answer 1

我现在懒得写任何代码，但你绝对应该能够通过递归而不是七个嵌套循环来做到这一点，而且事实上你应该能够设计一个适用于任意任意代码的方法-长度的电话号码。

基本思想是你会设计一个像这样的递归方法:

void recurse(String phone, int index, StringBuilder sb)
{
   // Get the number at position phone[index]
   // Loop through the possible letters for that particular number (eg. A, B, C):
      // Add the letter to the StringBuilder
      // Call recurse(phone, index + 1, sb)
      // Subtract last letter from the StringBuilder
}

每次递归时，您都在处理下一个数字/字母位置。

当然，如果您遇到终止条件(sb length == phone length)，那么您只需将 StringBuilder 的当前值写入文件并返回，而不是递归。

希望这对您有所帮助。

编辑:开始实际编写一些代码。真的很简单，不需要 LINQ:

   class Program
   {
      static Dictionary<Char, String> DigitMap = new Dictionary<Char, String>()
      {
         {'0', "0"},
         {'1', "1"},
         {'2', "ABC"},
         {'3', "DEF"},
         {'4', "GHI"},
         {'5', "JKL"},
         {'6', "MNO"},
         {'7', "PQRS"},
         {'8', "TUV"},
         {'9', "WXYZ"}
      };

      static void Main(string[] args)
      {
         String phone = Regex.Replace("867-5309", "[^0-9]", "");
         recurse(phone, 0, new StringBuilder());
      }

      static void recurse(String phone, int index, StringBuilder sb)
      {
         // Terminating condition
         if (index == phone.Length)
         {
            Console.WriteLine(sb.ToString());
            return;
         }

         // Get digit and letters string
         Char digit = phone[index];
         String letters = DigitMap[digit];

         // Loop through all letter combinations for digit
         foreach (Char c in letters)
         {
            sb.Append(c);
            recurse(phone, index + 1, sb);
            sb.Length -= 1;
         }
      }
   }
}

在此代码中(我制作了一个简单的控制台应用程序)我只是将文字写入控制台，但您可以将字符串添加到数组或将它们写入磁盘。