c# - 最短单词列表算法

Question

问题如下:用户提供了一个包含 X 个字母的 StartWord 和 EndWord 字符串，以及一个长度也为 X 的字符串列表(让它变成 4，但可能更多)

static void Main(string[] args)
{
    string StartWord = "Spot";
    string EndWord = "Spin";
    List<string> providedList = new List<string>
                                {
                                "Spin", "Spit", "Spat", "Spot", "Span"
                                };
    List<string> result = MyFunc(StartWord, EndWord, providedList);
}

public List<string> MyFunc(string startWord, string endWord, List<string> input)
{
    ???
}

根据提供的参数，我需要向用户显示一个结果，该结果由最短的 4 个字母单词列表组成，以 StartWord 开始，以 EndWord 结束，其中包含许多可在列表中找到的中间单词，其中每个单词与前一个单词的区别恰好是一个字母。

例如，上面的代码应该返回包含这些元素的字符串列表: Spot(作为 FirstWord)， 吐(只有一个字母与前一个单词不同)， 旋转(作为 EndWord)

一个不好的例子是:Spot、Spat、Span、Spin(因为与上述 2 项相比需要 3 项更改)

我一直在研究一些匹配算法和递归，但我不知道该怎么做。

提前感谢您提供的任何帮助。

Answer 1

创建一个图，其中顶点是单词，边连接任意两个相差一个字母的单词。

进行广度优先搜索，从 StartWord 开始，寻找到 EndWord 的最短路径。

---

这是此解决方案的另一种语言 (Python) 示例代码。这可能会给你一个更好的指导。 :-)

def shortestWordPath (startWord, endWord, words):
    graph = {}
    for word in words:
        graph[word] = {"connected": []}
    for word in words:
        for otherWord in words:
            if 1 == wordDistance(word, otherWord):
                graph[word]['connected'].append(otherWord)
    todo = [(startWord,0)]
    while len(todo):
        (thisWord, fromWord) = todo.pop(0)
        if thisWord == endWord:
            answer = [thisWord, fromWord]
            while graph[ answer[-1] ]["from"] != 0:
                answer.append(graph[ answer[-1] ]["from"])
            answer.reverse()
            return answer
        elif "from" in graph[thisWord]:
            pass # We have already processed this.
        else:
            graph[thisWord]["from"] = fromWord
            for nextWord in graph[thisWord]["connected"]:
                todo.append([nextWord, thisWord])
    return None


def wordDistance (word1, word2):
    return len(differentPositions(word1, word2))

def differentPositions(word1, word2):
    answer = []
    for i in range(0, min(len(word1), len(word2))):
        if word1[i] != word2[i]:
            answer.append(i)
    for i in range(min(len(word1), len(word2)),
                   max(len(word1), len(word2))):
        answer.append(i)
    return answer

print shortestWordPath("Spot", "Spin",
    ["Spin", "Spit", "Spat", "Spot", "Span"])