通过有效词将一个词转换成另一个词的algorithm
我遇到了编辑距离问题的这种变化：
devise一个将源词转换为目标词的algorithm。 例如：从头到尾，在每一步中，你只需要replace一个字符，而这个字就必须是有效的。 你会得到一本字典。
这显然是编辑距离问题的一个变种，但在编辑距离，我不在乎这个单词是否有效。 那么如何添加这个要求来编辑距离。
这可以被模拟为一个graphics问题。 您可以将这些词作为图的节点，并且两个节点连接，当且仅当它们具有相同的长度并且在一个字符中不同时。
您可以预处理字典并创build此图，应该看起来像：
stack jack | | | | smack back -- pack -- pick 然后你可以从单词到表示单词的节点的映射，为此可以使用散列表，高度平衡的BST …
一旦完成了上述映射，您所要做的就是查看两个graphics节点之间是否存在path，这可以使用BFS或DFS轻松完成。
所以你可以总结algorithm如下：
preprocess the dictionary and create the graph. Given the two inputs words w1 and w2 if length(w1) != length(w2) Not possible to convert else n1 = get_node(w1) n2 = get_node(w2) if(path_exists(n1,n2)) Possible and nodes in the path represent intermediary words else Not possible
codaddict的图方法是有效的，但是要花费O（n ^ 2）时间来构build每个图，其中n是给定长度的字的数量。 如果这是一个问题，可以更有效地构build一个bk树 ，这使得可以find具有给定编辑距离（在本例中为1）的目标单词的所有单词。
我不认为这是编辑距离。
我认为这可以使用graphics来完成。 只需从字典中构build一个graphics，并尝试使用您最喜欢的graphics遍历algorithm导航到目的地。
创build一个图表，每个节点代表字典中的单词。 如果两个单词节点之间的对应词的编辑距离为1，则在两个单词节点之间添加一条边。那么所需的最小变换次数就是源节点和目的节点之间的最短path长度。
您可以简单地使用recursion反向跟踪，但这远不是最理想的解决scheme。
# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only # one letter at a time. The new word you get in each step must be in the # dictionary. # def transform(english_words, start, end): # transform(english_words, 'damp', 'like') # ['damp', 'lamp', 'limp', 'lime', 'like'] # ['damp', 'camp', 'came', 'lame', 'lime', 'like'] def is_diff_one(str1, str2): if len(str1) != len(str2): return False count = 0 for i in range(0, len(str1)): if str1[i] != str2[i]: count = count + 1 if count == 1: return True return False potential_ans = [] def transform(english_words, start, end, count): global potential_ans if count == 0: count = count + 1 potential_ans = [start] if start == end: print potential_ans return potential_ans for w in english_words: if is_diff_one(w, start) and w not in potential_ans: potential_ans.append(w) transform(english_words, w, end, count) potential_ans[:-1] return None english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like']) transform(english_words, 'damp', 'lame', 0)
这是使用BFS解决问题的C＃代码：
//use a hash set for a fast check if a word is already in the dictionary static HashSet<string> Dictionary = new HashSet<string>(); //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node static Dictionary<string, string> parents = new Dictionary<string, string>(); public static List<string> FindPath(List<string> input, string start, string end) { char[] allcharacters = {'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'}; foreach (string s in input) Dictionary.Add(s); List<string> currentFrontier = new List<string>(); List<string> nextFrontier = new List<string>(); currentFrontier.Add(start); while (currentFrontier.Count > 0) { foreach (string s in currentFrontier) { for (int i = 0; i < s.Length; i++) { foreach (char c in allcharacters) { StringBuilder newWordBuilder = new StringBuilder(s); newWordBuilder[i] = c; string newWord = newWordBuilder.ToString(); if (Dictionary.Contains(newWord)) { //avoid traversing a previously traversed node if (!parents.Keys.Contains(newWord)) { parents.Add(newWord.ToString(), s); nextFrontier.Add(newWord); } } if (newWord.ToString() == end) { return ExtractPath(start, end); } } } } currentFrontier.Clear(); currentFrontier.Concat(nextFrontier); nextFrontier.Clear(); } throw new ArgumentException("The given dictionary cannot be used to get a path from start to end"); } private static List<string> ExtractPath(string start,string end) { List<string> path = new List<string>(); string current = end; path.Add(end); while (current != start) { current = parents[current]; path.Add(current); } path.Reverse(); return path; }
这显然是一个排列问题。 使用图表是矫枉过正的。 问题陈述缺less一个重要的约束条件; 你可以改变每个位置只有一次 。 这就隐含了解决scheme在4个步骤之内。 现在需要确定的是replace操作的顺序：
操作1 =将“H”更改为“T”
操作2 =将“E”更改为“A”
操作3 =将“A”更改为“I”
操作4 =将“D”更改为“L”
解决scheme，即操作顺序，是string“1234”的一些排列，其中每个数字表示被replace的字符的位置。 例如“3124”表示首先应用操作3，然后操作1，然后操作2，然后操作4.在每一步，如果结果词不在词典中，则跳到下一个排列。 合理的微不足道。 编码任何人？
