Final: Word Ladder

Lab Java Advanced 30 points

Turn a start word into an end word by changing one letter at a time, where every in-between word must be in the dictionary. Print the fewest words in the ladder, counting both the start and the end, or 0 if it can't be done. All words have the same length.

Input

Line 1: start end. Line 2: n. Line 3: n dictionary words (the end word must be among them to be reachable).

Output

The ladder length, or 0.

Example

Input

cold warm
6
cord card ward warm word worm

Output

Sample input available Sample output available

Editor

Java

Hints

Each word is a node; two words are linked if they differ in one letter. Fewest steps → BFS.

Instead of comparing with every dictionary word, try changing each letter to 'a'..'z' and look it up in a HashSet.

Solution explanation

BFS over words, with O(1) HashSet lookups for the neighbours: about O(n × L × 26) for words of length L. It combines a graph, a queue, a set and a map.

Show solution

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String start = sc.next(), end = sc.next();
        int n = sc.nextInt();
        HashSet<String> dict = new HashSet<String>();
        for (int i = 0; i < n; i++) dict.add(sc.next());

        HashMap<String, Integer> steps = new HashMap<String, Integer>();
        ArrayDeque<String> queue = new ArrayDeque<String>();
        steps.put(start, 1);
        queue.offer(start);
        while (!queue.isEmpty()) {
            String word = queue.poll();
            if (word.equals(end)) {
                System.out.println(steps.get(word));
                return;
            }
            char[] letters = word.toCharArray();
            for (int i = 0; i < letters.length; i++) {
                char original = letters[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == original) continue;
                    letters[i] = ch;
                    String next = new String(letters);
                    if (dict.contains(next) && !steps.containsKey(next)) {
                        steps.put(next, steps.get(word) + 1);
                        queue.offer(next);
                    }
                }
                letters[i] = original;
            }
        }
        System.out.println(0);
    }
}

Output

Answer