[Leetcode] 有人做过leetcode里的word ladder II 吗？
Given two words (start and end),and a dictionary, find all shortest transformation sequence(s) from start toend,such that:1.Only one letter can be changed at a time2.Each intermediate word must exist in thedictionaryFor example,Given:start = "hit"end = "cog"dict =["hot","dot","dog","lot","log"]Return:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"Note:·All words have the same length.·All words contain only lowercasealphabetic characters. 没做过，随便谈谈自己想法。把dictionary按照是否相连做个图，o(n^2）然后把start和dictionary中每个只差一个字母的连条边,o(n)，end也如此连若干条边 o(n)。然后BFS？ o(m+n)不知有没有优化了楼主的算法。另外我觉得这题很坑的。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母用O(n^2)的好像就会超时，于是只能对每个单词，枚举与它只有一个字母不同的所有单词，看是否在dict里，这样就是26*l(单词长度) * n * 查dict的时间(认为是常数吧) 没做过，随便谈谈自己想法。把dictionary按照是否相连做个图，o(n^2）然后把start和dictionary中每个只差一个字母的连条边,o(n)，end也如此连若干条边 o(n)。然后BFS？ o(m+n)不知有没有优化了楼主的算法。另外我觉得这题很坑的。关键在于一开始，要建立一个图，看dict中任意两个单词是否只差一个字母用O(n^2)的好像就会超时，于是只能对每个单词，枚举与它只有一个字母不同的所有单词，看是否在dict里，这样就是26*l(单词长度) * n * 查dict的时间(认为是常数吧)
页:
[1]