## Question

### Problem Statement

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

#### Example

Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

#### Note

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

## 题解

1. start 和 end 相等。
2. end 在 dict 中，且 start 可以转换为 dict 中的一个单词。
3. end 不在 dict 中，但可由 start 或者 dict 中的一个单词转化而来。
4. end 无法由 start 转化而来。

### Java

public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null && end == null) return 0;
if (start.length() == 0 && end.length() == 0) return 0;
assert(start.length() == end.length());
if (dict == null || dict.size() == 0) {
return 0;
}

Set<String> hash = new HashSet<String>();
q.offer(start);
while (!q.isEmpty()) {
int qLen = q.size();
for (int i = 0; i < qLen; i++) {
String strTemp = q.poll();

for (String nextWord : getNextWords(strTemp, dict)) {
// filter visited word in the dict
if (hash.contains(nextWord)) continue;
q.offer(nextWord);
}
}
}

return 0;
}

private Set<String> getNextWords(String curr, Set<String> dict) {
Set<String> nextWords = new HashSet<String>();
for (int i = 0; i < curr.length(); i++) {
char[] chars = curr.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String temp = new String(chars);
if (dict.contains(temp)) {
}
}
}

return nextWords;
}
}


### 源码分析

#### BFS 和哈希表的配合使用

BFS 用作搜索，哈希表用于记录已经访问节点。在可以改变输入数据的前提下，需要将 end 加入 dict 中，否则对于不在 dict 中出现的 end 会有问题。
{"ft_lang_label":"__label__zh","ft_lang_prob":0.5301616,"math_prob":0.9746649,"size":3002,"snap":"2023-40-2023-50","text_gpt3_token_len":1401,"char_repetition_ratio":0.12708472,"word_repetition_ratio":0.01459854,"special_character_ratio":0.27448368,"punctuation_ratio":0.16342412,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98394966,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-25T20:02:32Z\",\"WARC-Record-ID\":\"<urn:uuid:d007e445-0b69-4aa1-b1fd-9632c2399db5>\",\"Content-Length\":\"122819\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7383f4f7-0140-4d0b-bb0c-a0d3702c0869>\",\"WARC-Concurrent-To\":\"<urn:uuid:373c666d-780b-4879-9368-e463bca2594c>\",\"WARC-IP-Address\":\"185.199.108.153\",\"WARC-Target-URI\":\"https://algorithm.yuanbin.me/zh-hans/graph/word_ladder.html\",\"WARC-Payload-Digest\":\"sha1:EUY2ZBTAT2KUKYRYNYCJTGGGRXTSVW3G\",\"WARC-Block-Digest\":\"sha1:GP7E5PNQING7YMF4AECVBST5JD7UTSDO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233510085.26_warc_CC-MAIN-20230925183615-20230925213615-00709.warc.gz\"}"}