\u5b57\u5178 \u7ed9\u4f60\u4e24\u4e2a\u5355\u8bcd \u793a\u4f8b 1\uff1a<\/strong><\/p>\n \u8f93\u5165\uff1abeginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] \u793a\u4f8b 2\uff1a<\/strong><\/p>\n \u8f93\u5165\uff1abeginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] \u5355\u8bcd\u63a5\u9f99 \u5b57\u5178 wordList \u4e2d\u4ece\u5355\u8bcd beginWord \u548c endWord \u7684 \u8f6c\u6362\u5e8f\u5217 \u662f\u4e00\u4e2a\u6309\u4e0b\u8ff0\u89c4\u683c\u5f62\u6210\u7684\u5e8f\u5217 be …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[31,5,9],"class_list":["post-249","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-bfs","tag-java","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/249","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/comments?post=249"}],"version-history":[{"count":1,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/249\/revisions"}],"predecessor-version":[{"id":250,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/249\/revisions\/250"}],"wp:attachment":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/media?parent=249"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/categories?post=249"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/tags?post=249"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}wordList<\/code> \u4e2d\u4ece\u5355\u8bcd beginWord<\/code> \u548c endWord<\/code> \u7684 \u8f6c\u6362\u5e8f\u5217 \u662f\u4e00\u4e2a\u6309\u4e0b\u8ff0\u89c4\u683c\u5f62\u6210\u7684\u5e8f\u5217 beginWord -> s1 -> s2 -> ... -> sk<\/code>\uff1a<\/p>\n\n
1 <= i <= k<\/code> \u65f6\uff0c\u6bcf\u4e2a si<\/code> \u90fd\u5728 wordList<\/code> \u4e2d\u3002\u6ce8\u610f\uff0c beginWord<\/code> \u4e0d\u9700\u8981\u5728 wordList<\/code> \u4e2d\u3002<\/li>\nsk == endWord<\/code><\/li>\n<\/ul>\nbeginWord<\/code> \u548c endWord<\/code> \u548c\u4e00\u4e2a\u5b57\u5178 wordList<\/code> \uff0c\u8fd4\u56de \u4ece beginWord<\/code> \u5230 endWord<\/code> \u7684 \u6700\u77ed\u8f6c\u6362\u5e8f\u5217 \u4e2d\u7684 \u5355\u8bcd\u6570\u76ee \u3002\u5982\u679c\u4e0d\u5b58\u5728\u8fd9\u6837\u7684\u8f6c\u6362\u5e8f\u5217\uff0c\u8fd4\u56de 0<\/code> \u3002<\/p>\n\n
\n\u8f93\u51fa\uff1a5
\n\u89e3\u91ca\uff1a\u4e00\u4e2a\u6700\u77ed\u8f6c\u6362\u5e8f\u5217\u662f "hit" -> "hot" -> "dot" -> "dog" -> "cog", \u8fd4\u56de\u5b83\u7684\u957f\u5ea6 5\u3002<\/p>\n<\/blockquote>\n\n
\n\u8f93\u51fa\uff1a0
\n\u89e3\u91ca\uff1aendWord "cog" \u4e0d\u5728\u5b57\u5178\u4e2d\uff0c\u6240\u4ee5\u65e0\u6cd5\u8fdb\u884c\u8f6c\u6362\u3002<\/p>\n<\/blockquote>\n\u89e3\u6cd51 \u53cc\u5411BFS \u901f\u5ea6\u6700\u5feb\u89e3\u6cd5 3hashset\u63d0\u901f<\/h2>\n
class Solution {\n public int ladderLength(String beginWord, String endWord, List<String> wordList) {\n if (!wordList.contains(endWord)) {\n return 0;\n }\n\n Set<String> start = new HashSet<>();\n Set<String> end = new HashSet<>();\n Set<String> dic = new HashSet<>(wordList);\n\n start.add(beginWord);\n end.add(endWord);\n int step = 1;\n\n while (!start.isEmpty() && !end.isEmpty()) {\n Set<String> tmp = new HashSet<>();\n\n for (String cur : start) {\n if (end.contains(cur)) {\n return step;\n }\n\n char[] cs = cur.toCharArray();\n \/\/ \u4f18\u53162\n for (int i = 0; i < cs.length; i++) {\n char temp = cs[i];\n \/\/ \u53d8\u5316\n for (char c = 'a'; c <= 'z'; c++) {\n if (c == temp) {\n continue;\n }\n cs[i] = c;\n String nCur = new String(cs);\n if (dic.contains(nCur)) {\n if (end.contains(nCur)) {\n return step + 1;\n } else {\n tmp.add(nCur);\n }\n }\n }\n \/\/ \u590d\u539f\n cs[i] = temp;\n }\n }\n step++;\n dic.removeAll(start);\n start = end;\n end = tmp;\n\n \/\/ \u4f18\u53163\n if (start.size() > end.size()) {\n tmp = start;\n start = end;\n end = tmp;\n }\n }\n return 0;\n }\n}<\/code><\/pre>\n\u89e3\u6cd52 \u5148\u5efa\u56fe\uff0c\u518dbfs\uff0c\u65b9\u6cd5\u542f\u53d1\u6027\u5f3a<\/h2>\n
class Solution {\n Map<String, Integer> wordId = new HashMap<String, Integer>();\n List<List<Integer>> edge = new ArrayList<List<Integer>>();\n int nodeNum = 0;\n\n public int ladderLength(String beginWord, String endWord, List<String> wordList) {\n for (String word : wordList) {\n addEdge(word);\n }\n addEdge(beginWord);\n if (!wordId.containsKey(endWord)) {\n return 0;\n }\n int[] dis = new int[nodeNum];\n Arrays.fill(dis, Integer.MAX_VALUE);\n int beginId = wordId.get(beginWord), endId = wordId.get(endWord);\n dis[beginId] = 0;\n\n Queue<Integer> que = new LinkedList<Integer>();\n que.offer(beginId);\n while (!que.isEmpty()) {\n int x = que.poll();\n if (x == endId) {\n return dis[endId] \/ 2 + 1;\n }\n for (int it : edge.get(x)) {\n if (dis[it] == Integer.MAX_VALUE) {\n dis[it] = dis[x] + 1;\n que.offer(it);\n }\n }\n }\n return 0;\n }\n\n public void addEdge(String word) {\n addWord(word);\n int id1 = wordId.get(word);\n char[] array = word.toCharArray();\n int length = array.length;\n for (int i = 0; i < length; ++i) {\n char tmp = array[i];\n array[i] = '*';\n String newWord = new String(array);\n addWord(newWord);\n int id2 = wordId.get(newWord);\n edge.get(id1).add(id2);\n edge.get(id2).add(id1);\n array[i] = tmp;\n }\n }\n\n public void addWord(String word) {\n if (!wordId.containsKey(word)) {\n wordId.put(word, nodeNum++);\n edge.add(new ArrayList<Integer>());\n }\n }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"