# 0127. Word Ladder

<https://leetcode.com/problems/word-ladder>

## Description

A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

* Every adjacent pair of words differs by a single letter.
* Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
* `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return *the **number of words** in the **shortest transformation sequence** from* `beginWord` *to* `endWord`*, or* `0` *if no such sequence exists.*

**Example 1:**

```
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
**Output:** 5
**Explanation:** One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
```

**Example 2:**

```
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
**Output:** 0
**Explanation:** The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
```

**Constraints:**

* `1 <= beginWord.length <= 10`
* `endWord.length == beginWord.length`
* `1 <= wordList.length <= 5000`
* `wordList[i].length == beginWord.length`
* `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
* `beginWord != endWord`
* All the words in `wordList` are **unique**.

## ac1: Graph + BFS

12/22/2017

very time consuming in building the graph Buiding the graph is awaste of time here.

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        wordList.add(beginWord);
        int begin = wordList.size() - 1;
        int end = -1;

        // Build graph, iterate wordlist get edges.
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < wordList.size(); i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < wordList.size(); i++) {
            if (wordList.get(i).equals(endWord)) end = i;
            for (int j = i + 1; j < wordList.size(); j++) {
                if (isConnected(wordList.get(i), wordList.get(j))) {
                    adjList.get(i).add(j);
                    adjList.get(j).add(i);
                }
            }
        }

        // BFS
        int layer = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        boolean[] visited = new boolean[wordList.size()];
        q.offer(begin);
        while (!q.isEmpty()) {
            int len = q.size();
            layer++;
            for (int i = 0; i < len; i++) {
                int head = q.poll();
                visited[head] = true;
                for (int next : adjList.get(head)) {
                    if (visited[next]) continue;
                    if (next == end) return layer+1;
                    q.offer(next);
                }
            }

        }

        // can't find
        return 0;
    }
    private boolean isConnected(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) diff++;
        }
        return diff == 1;
    }
}
```

## ac2: BFS

Simpler and much faster. iterate through word is much faster iterate wordList.

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<String>(wordList);

        int layer = 0;

        Queue<String> q = new LinkedList<String>();
        q.offer(beginWord);
        while (!q.isEmpty()) {
            int len = q.size();
            layer++;
            for (int i = 0; i < len; i++) {
                String head = q.poll();
                // get head's adjcent words in dict
                for (int l = 0; l < head.length(); l++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[l] = c;
                        String headDiff = String.valueOf(chars);
                        if (wordSet.contains(headDiff)){
                            if (headDiff.equals(endWord)) return layer + 1; // Find endword, return.
                            q.offer(headDiff);
                            wordSet.remove(headDiff);
                        }
                    }
                }
            }
        }

        return 0;
    }

}
```

## ac3: bidirectional BFS

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // edge cases
        if (wordList == null || wordList.size() == 0) return 0;

        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Set<String> visited = new HashSet<>();
        Set<String> beginSet = new HashSet<>();
        beginSet.add(beginWord);
        Set<String> endSet = new HashSet<>();
        endSet.add(endWord);

        int len = 0;
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set<String> tmp = beginSet;
                beginSet = endSet;
                endSet = tmp;
            }

            len++;
            Set<String> tmpSet = new HashSet<>();
            for(String w : beginSet) {
                char[] chars = w.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char old = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String newWord = String.valueOf(chars);
                        if (wordSet.contains(newWord)) {
                            if (endSet.contains(newWord)) return len + 1;
                            if (!visited.contains(newWord)) {
                                tmpSet.add(newWord);
                                visited.add(newWord);
                            }
                        }
                    }
                    chars[i] = old;
                }
            }
            beginSet = tmpSet;
        }


        return 0; // can't find
    }
}
/*
BFS
Queue<String> q
transform word 1 letter a step, lookup in dict, if contains, add to queue, if == endword return
return 0;
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0127-word-ladder.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.