Treat each word as a node in a graph and connect words that differ by exactly one letter.

Word Ladder

hard

Acceptance: 38%

GraphsBFS

Starting from a given word, transform it into a target word by changing one letter at a time. Every intermediate word must exist in a provided dictionary. Find the length of the shortest such transformation chain (counting both endpoints). Return 0 if no chain exists.

Examples

Example 1:

Input:beginWord = "cat", endWord = "dog", wordList = ["cot","dot","dog","cog","dat"]

Output:4

Explanation: cat -> cot -> cog -> dog (4 words).

Example 2:

Input:beginWord = "run", endWord = "fly", wordList = ["fun","fin","fry"]

Output:0

Explanation: The end word 'fly' is not in the dictionary.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Word Ladder

Examples

Hints

Related Problems