Question

Formatted question description: https://leetcode.ca/all/127.html

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> s_k such that:

Every adjacent pair of words differs by a single letter.
Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
s_k == 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.

Algorithm

To improve the search efficiency of our dictionary, we can use a HashSet to store all the words in the dictionary.

Next, we can create a HashMap to establish a mapping between the last word in a path and the length of the path, with the starting word mapped to 1.

To implement the BFS algorithm, we will use a queue data structure. We add the starting word to the queue and start looping over it. At each iteration, we dequeue the first word in the queue and generate all possible replacement words by replacing each character with all 26 letters.

If a replacement word is equal to the target word, we retrieve its length from the hash table and increment it by one.

If a replacement word exists in the dictionary but not in the hash table, we enqueue the replacement word and map its value in the hash table to the previous word’s value plus one.

Once we have dequeued all possible words from the queue and there are no more possible paths to the target word, we return 0 to indicate that there is no path from the start word to the target word in the dictionary.

Code

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        int ans = 1;
        while (!q.isEmpty()) {
            ++ans;
            for (int i = q.size(); i > 0; --i) {
                String s = q.poll();
                char[] chars = s.toCharArray();
                for (int j = 0; j < chars.length; ++j) {
                    char ch = chars[j];
                    for (char k = 'a'; k <= 'z'; ++k) {
                        chars[j] = k;
                        String t = new String(chars);
                        if (!words.contains(t)) {
                            continue;
                        }
                        if (endWord.equals(t)) {
                            return ans;
                        }
                        q.offer(t);
                        words.remove(t);
                    }
                    chars[j] = ch;
                }
            }
        }
        return 0;
    }
}

public class Word_Ladder {

    public class Solution {
        public int ladderLength(String start, String end, Set<String> dict) {

            // bfs to make sure its shortest

            if (start.equals(end)) {
                return 0;
            }

            dict.add(end); // !!!@note: 别忘了

            Queue<String> q = new LinkedList<String>();
            HashSet<String> visited = new HashSet<String>();
            int level = 1;
            int currentLevelCount = 1;
            int newLevelCount = 0;

            q.offer(start);
            visited.add(start);

            while (!q.isEmpty()) {

                String s = q.poll();
                currentLevelCount--; // @note: 这样少了queue的操作

                for (int i = 0; i < s.length(); i++) {
                    char[] array = s.toCharArray(); // @note:@memorize: char array的效率要高

                    for (char c = 'a'; c <= 'z'; c++) {
                        array[i] = c;
                        String each = new String(array);

                        if (each.equals(end)) {
                            return level + 1;
                        }

                        // @note: 这里没有检查是不是string生成了他自己，因为自己已经在visited里面了。但是还是不太明显，不推荐。
                        //          加一个if没什么，逻辑更清晰
                        if (dict.contains(each) && !visited.contains(each)) {
                            q.offer(each);
                            visited.add(each);
                            newLevelCount++;
                        }
                    }
                }

                // @note: must be after trying the last word of currentLevel, then update
                if (currentLevelCount == 0) {
                    currentLevelCount = newLevelCount;
                    newLevelCount = 0;
                    level++;

                }

            }

            return 0; // 如果没找到，那么就是0
        }

    }

    // 不用string接起来，直接char[]
    public class Solution_bfs_over_time {
        public int ladderLength(String start, String end, Set<String> dict) {

            // bfs to make sure its shortest

            if (start.equals(end))  return 0;

            dict.add(end); // !!!@note: 别忘了

            Queue<String> q = new LinkedList<String>();
            HashSet<String> visited = new HashSet<String>();
            int count = 1;

            q.offer(start);
            q.offer(null); // null is used marking level end

            while (!q.isEmpty()) {

                if (q.peek() == null) {
                    count++;
                    q.poll(); // pop null at head

                    // @note@note: or else, null poll, nulll offer. infinite looping
                    if (q.isEmpty())
                        break;
                    else {
                        q.offer(null); // enqueue new null
                        continue;
                    }
                }

                String s = q.poll();
                visited.add(s);

                char[] array = s.toCharArray();
                for (int i = 0; i < s.length(); i++) {
                    char ati = array[i];

                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == ati)   continue;
                        array[i] = c;
                        String each = new String(array);
                        if (dict.contains(each)) {

                            if (visited.contains(each))     continue;
                            if (each.equals(end))   return count + 1;

                            q.offer(each);
                        }
                    }

                    array[i] = ati;
                }

            }

            return 0;
        }

    }


    public class Solution_recursion_over_time {
        Set<String> used = new HashSet<>();
        int min = Integer.MAX_VALUE;

        // return: 5
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {

            // @note@memorize: System.out.println(one.ladderLength("hit", "cog", new HashSet<String>(Arrays.asList("hot","dot","dog","lot","log"))));
            if (beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0) {
                return 0;
            }

            // @note: test on char
            // System.out.println('a' + 1); // output: 98
            // System.out.println((char)('a' + 1)); // output: b

            used.add(beginWord); // @note: dont forget adding it
            wordList.add(endWord); // @note: dont forget !!! when checking one-step-word validity, endWord should be valid...
            findLadder(beginWord, endWord, wordList, 0); // begin and end are same, then length==0

            return min;
        }

        private void findLadder(String beginWord, String endWord, Set<String> wordList, int count) {

            if (beginWord.equals(endWord)) {
                min = Math.min(min, count);

                return;
            }

            List<String> all = getWordsOneStepAndInDict(beginWord, wordList);

            // System.out.println(all.toString());

            if (all.size() == 0) {
                return;
            }

            for (int i = 0; i < all.size(); i++) {

                String next = all.get(i);

                used.add(next);
                findLadder(next, endWord, wordList, count + 1);
                // used.remove(used.size() - 1); // @note:@memorize: HashSet is not remove(index), but remove(object)
                used.remove(used.size() - 1);
            }
        }

        private boolean isValidWord(String w, Set<String> wordList) {
            return wordList.contains(w) && !used.contains(w);
        }

        private List<String> getWordsOneStepAndInDict(String w, Set<String> wordList) {

            List<String> result = new ArrayList<>(); // 26 chars, except itself

            // length * 26, still o(n) though
            for (int pos = 0; pos < w.length(); pos++) {
                for (int i = 0; i <= 25; i++) {

                    char newChar = (char)('a' + i);

                    if (w.charAt(pos) != newChar) {

                        String one = w.substring(0, pos) + newChar + w.substring(pos + 1);

                        if (isValidWord(one, wordList)) { // @note: important, avoid infinite looping
                            result.add(one);
                        }
                    }
                }
            }

            return result;
        }
    }

}

############

class Solution {
    private Set<String> words;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        words = new HashSet<>(wordList);
        if (!words.contains(endWord)) {
            return 0;
        }
        Queue<String> q1 = new ArrayDeque<>();
        Queue<String> q2 = new ArrayDeque<>();
        Map<String, Integer> m1 = new HashMap<>();
        Map<String, Integer> m2 = new HashMap<>();
        q1.offer(beginWord);
        q2.offer(endWord);
        m1.put(beginWord, 0);
        m2.put(endWord, 0);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
            if (t != -1) {
                return t + 1;
            }
        }
        return 0;
    }

    private int extend(Map<String, Integer> m1, Map<String, Integer> m2, Queue<String> q) {
        for (int i = q.size(); i > 0; --i) {
            String s = q.poll();
            int step = m1.get(s);
            char[] chars = s.toCharArray();
            for (int j = 0; j < chars.length; ++j) {
                char ch = chars[j];
                for (char k = 'a'; k <= 'z'; ++k) {
                    chars[j] = k;
                    String t = new String(chars);
                    if (!words.contains(t) || m1.containsKey(t)) {
                        continue;
                    }
                    if (m2.containsKey(t)) {
                        return step + 1 + m2.get(t);
                    }
                    q.offer(t);
                    m1.put(t, step + 1);
                }
                chars[j] = ch;
            }
        }
        return -1;
    }
}

// OJ: https://leetcode.com/problems/word-ladder/
// Time: O(N * W^2)
// Space: O(NW)
class Solution {
public:
    int ladderLength(string B, string E, vector<string>& A) {
        unordered_set<string> head, tail, s(begin(A), end(A));
        if (s.count(E) == 0) return 0;
        head.insert(B);
        tail.insert(E);
        s.erase(B);
        s.erase(E);
        int ans = 2;
        while (head.size() && tail.size()) {
            if (head.size() > tail.size()) swap(head, tail);
            unordered_set<string> next;
            for (auto w : head) {
                for (char &c : w) {
                    char tmp = c;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        c = ch;
                        if (tail.count(w)) return ans;
                        if (s.count(w) == 0) continue;
                        next.insert(w);
                        s.erase(w);
                    }
                    c = tmp;
                }
            }
            ++ans;
            swap(head, next);
        }
        return 0;
    }
};

# native BFS
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        q = deque([beginWord])
        ans = 1
        while q:
            ans += 1
            for _ in range(len(q)):
                s = q.popleft()
                s = list(s) # must convert to list, cannot directly update s[i]='a'
                for i in range(len(s)):
                    ch = s[i]
                    for j in range(26):
                        # will re-generate s itself
                        # but s not in words-set, s removed after added to words-set
                        s[i] = chr(ord('a') + j)
                        t = ''.join(s)
                        if t not in words:
                            continue
                        if t == endWord:
                            return ans
                        q.append(t)
                        words.remove(t) # equivalent to set t as visited
                    s[i] = ch # restore
        return 0


#########

'''
双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：

1. 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
2. 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
3. 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
4. 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。
'''
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def extend(m1, m2, q):
            for _ in range(len(q)):
                s = q.popleft() # so, every time, starting from start-word... and later if t in m1 will skip repeated part...
                step = m1[s]
                s = list(s) # s = "abc", list(s) ==> ['a', 'b', 'c']
                for i in range(len(s)):
                    ch = s[i]
                    for j in range(26):
                        s[i] = chr(ord('a') + j)
                        t = ''.join(s)
                        if t in m1 or t not in words:
                            continue
                        if t in m2:
                            return step + 1 + m2[t]
                        m1[t] = step + 1
                        q.append(t)
                    s[i] = ch
            return -1

        words = set(wordList)
        if endWord not in words:
            return 0
        q1, q2 = deque([beginWord]), deque([endWord])
        m1, m2 = {beginWord: 0}, {endWord: 0}
        while q1 and q2:
            t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
            if t != -1:
                return t + 1
        return 0

#########

import string
from collections import deque


class Solution(object):
  def ladderLength(self, beginWord, endWord, wordList):
    """
    :type beginWord: str
    :type endWord: str
    :type wordList: Set[str]
    :rtype: int
    """

    def getNbrs(src, dest, wordList):
      res = []
      for c in string.ascii_lowercase:
        for i in range(0, len(src)):
          newWord = src[:i] + c + src[i + 1:]
          if newWord == src:
            continue
          if newWord in wordList or newWord == dest:
            # about yield https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python
            # yield is a keyword that is used like return, except the function will return a generator.
            yield newWord

    queue = deque([beginWord])
    length = 0
    while queue:
      length += 1
      for k in range(0, len(queue)):
        top = queue.popleft()
        for nbr in getNbrs(top, endWord, wordList):
          wordList.remove(nbr)
          if nbr == endWord:
            return length + 1
          queue.append(nbr)
    return 0

func ladderLength(beginWord string, endWord string, wordList []string) int {
	words := make(map[string]bool)
	for _, word := range wordList {
		words[word] = true
	}
	if !words[endWord] {
		return 0
	}

	q1, q2 := []string{beginWord}, []string{endWord}
	m1, m2 := map[string]int{beginWord: 0}, map[string]int{endWord: 0}
	extend := func() int {
		for i := len(q1); i > 0; i-- {
			s := q1[0]
			step, _ := m1[s]
			q1 = q1[1:]
			chars := []byte(s)
			for j := 0; j < len(chars); j++ {
				ch := chars[j]
				for k := 'a'; k <= 'z'; k++ {
					chars[j] = byte(k)
					t := string(chars)
					if !words[t] {
						continue
					}
					if _, ok := m1[t]; ok {
						continue
					}
					if v, ok := m2[t]; ok {
						return step + 1 + v
					}
					q1 = append(q1, t)
					m1[t] = step + 1
				}
				chars[j] = ch
			}
		}
		return -1
	}
	for len(q1) > 0 && len(q2) > 0 {
		if len(q1) > len(q2) {
			m1, m2 = m2, m1
			q1, q2 = q2, q1
		}
		t := extend()
		if t != -1 {
			return t + 1
		}
	}
	return 0
}

using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        var words = Enumerable.Repeat(beginWord, 1).Concat(wordList).Select((word, i) => new { Word = word, Index = i }).ToList();
        var endWordIndex = words.Find(w => w.Word == endWord)?.Index;
        if (endWordIndex == null) {
            return 0;
        }

        var paths = new List<int>[words.Count];
        for (var i = 0; i < paths.Length; ++i)
        {
            paths[i] = new List<int>();
        }
        for (var i = 0; i < beginWord.Length; ++i)
        {
            var hashMap = new Hashtable();
            foreach (var item in words)
            {
                var newWord = string.Format("{0}_{1}", item.Word.Substring(0, i), item.Word.Substring(i + 1));
                List<int> similars;
                if (!hashMap.ContainsKey(newWord))
                {
                    similars = new List<int>();
                    hashMap.Add(newWord, similars);
                }
                else
                {
                    similars = (List<int>)hashMap[newWord];
                }
                foreach (var similar in similars)
                {
                    paths[similar].Add(item.Index);
                    paths[item.Index].Add(similar);
                }
                similars.Add(item.Index);
            }
        }

        var left = words.Count - 1;
        var lastRound = new List<int> { 0 };
        var visited = new bool[words.Count];
        visited[0] = true;
        for (var result = 2; left > 0; ++result)
        {
            var thisRound = new List<int>();
            foreach (var index in lastRound)
            {
                foreach (var next in paths[index])
                {
                    if (!visited[next])
                    {
                        visited[next] = true;
                        if (next == endWordIndex) return result;
                        thisRound.Add(next);
                    }
                }
            }
            if (thisRound.Count == 0) break;
            lastRound = thisRound;
        }

        return 0;
    }
}

127 - Word Ladder

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions