如何使用矩阵中的相邻字母查找所有可能的单词

Question

我有以下测试矩阵:

a l i
g t m
j e a

我打算创建一个算法,帮助我只使用相邻的字母从给定的最小长度到最大长度找到每个可能的单词.

例如:

最少:3个字母

最多:6个字母

基于测试矩阵,我应该得到以下结果:

• 阿里
• ALM
• ALG
• ALT
• ATI
• 自动取款机
• ATG
• ...
• atmea

等等

我创建了一个测试代码(C#),它有一个代表字母的自定义类.

每个字母都知道它的邻居并且有一个生成计数器(用于在遍历期间跟踪它们).

这是它的代码:

public class Letter
{
    public int X { get; set; }
    public int Y { get; set; }

    public char Character { get; set; }

    public List<Letter> Neighbors { get; set; }

    public Letter PreviousLetter { get; set; }

    public int Generation { get; set; }

    public Letter(char character)
    {
        Neighbors = new List<Letter>();
        Character = character;
    }

    public void SetGeneration(int generation)
    {
        foreach (var item in Neighbors)
        {
            item.Generation = generation;
        }
    }
}

我想出如果我想要它是动态的,它必须基于递归.

不幸的是,以下代码创建了前4个单词,然后停止.毫无疑问,因为递归是由指定的生成级别停止的.

主要问题是递归只返回一个级别,但返回起点更好.

 private static void GenerateWords(Letter input, int maxLength, StringBuilder sb)
    {
        if (input.Generation >= maxLength)
        {               
            if (sb.Length == maxLength)
            {
                allWords.Add(sb.ToString());
                sb.Remove(sb.Length - 1, 1);
            }                
            return;
        }
        sb.Append(input.Character);
        if (input.Neighbors.Count > 0)
        {
            foreach (var child in input.Neighbors)
            {
                if (input.PreviousLetter == child)
                    continue;
                child.PreviousLetter = input;
                child.Generation = input.Generation + 1;
                GenerateWords(child, maxLength, sb);
            }
        }
    }

所以,我觉得有点卡住了,不知道我该怎么办？

Answer 1

从这里开始，您可以将其视为图遍历问题。您从每个给定的字母开始，找到长度为min_size到max_size的每个路径，其中 3 和 6 作为示例中的值。我建议使用递归例程，将单词构建为穿过网格的路径。这看起来像下面这样；用您的偏好替换类型和伪代码。

<array_of_string> build_word(size, current_node) {
    if (size == 1)  return current_node.letter as an array_of_string;
    result = <empty array_of_string>
    for each next_node in current_node.neighbours {
        solution_list = build_word(size-1, next_node);
        for each word in solution_list {
             // add current_node.letter to front of that word.
             // add this new word to the result array
        }
    }
    return the result array_of_string
}

这会让你走向解决方案吗？