Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Word Ladder

Hard · Graphs · Asked at Amazon, Google, Meta, Microsoft, LinkedIn

Transform begin into end by changing one letter at a time, where every intermediate word (and end) must be in the dictionary. Print the number of words in the shortest transformation sequence (counting begin and end), or 0 if it is impossible.

Input

First line: begin end. Second line: n. Third line: the n dictionary words. All words have the same length and are lowercase.

Output

The length of the shortest sequence, or 0.

Constraints

BFS over words. To find neighbours, try changing each position to each of the 26 letters and check a hash set.

Example 1

Input

hit cog
6
hot dot dog lot log cog

Output

5

Example 2

Input

hit cog
5
hot dot dog lot log

Output

0

Hints

  1. Every word is a node; words differing in exactly one letter are connected. You want the shortest path — BFS.
  2. Do not compare every pair of words. For a word, generate all variants with one letter changed (26 · length) and look them up in a hash set.

Approach

If end is not in the dictionary, print 0. BFS from begin with distance 1. For the word at the front of the queue, try every position and every letter; each variant that is in the dictionary and unvisited gets distance + 1 and is queued (remove it from the set to mark it visited). The first time end is popped, its distance is the number of words in the shortest sequence. If the queue empties, print 0.

Complexity: O(n · L · 26) time · O(n · L) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string b, e;
    int n;
    cin >> b >> e >> n;
    unordered_set<string> dict;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        dict.insert(w);
    }
    if (!dict.count(e)) {
        cout << 0 << "\n";
        return 0;
    }
    queue<pair<string, int>> q;
    q.push({b, 1});
    dict.erase(b);
    while (!q.empty()) {
        string w = q.front().first;
        int d = q.front().second;
        q.pop();
        if (w == e) {
            cout << d << "\n";
            return 0;
        }
        for (size_t p = 0; p < w.size(); p++) {
            char orig = w[p];
            for (char c = 'a'; c <= 'z'; c++) {
                w[p] = c;
                if (dict.count(w)) {
                    dict.erase(w);
                    q.push({w, d + 1});
                }
            }
            w[p] = orig;
        }
    }
    cout << 0 << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

data = sys.stdin.read().split()
b, e, n = data[0], data[1], int(data[2])
words = set(data[3 : 3 + n])
ans = 0
if e in words:
    words.discard(b)
    q = deque([(b, 1)])
    while q:
        w, d = q.popleft()
        if w == e:
            ans = d
            break
        for p in range(len(w)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                x = w[:p] + c + w[p + 1 :]
                if x in words:
                    words.discard(x)
                    q.append((x, d + 1))
print(ans)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String b = sc.next(), e = sc.next();
        int n = sc.nextInt();
        Set<String> dict = new HashSet<>();
        for (int i = 0; i < n; i++) dict.add(sc.next());
        if (!dict.contains(e)) {
            System.out.println(0);
            return;
        }
        dict.remove(b);
        ArrayDeque<String> q = new ArrayDeque<>();
        Map<String, Integer> dist = new HashMap<>();
        q.add(b);
        dist.put(b, 1);
        while (!q.isEmpty()) {
            String w = q.poll();
            int d = dist.get(w);
            if (w.equals(e)) {
                System.out.println(d);
                return;
            }
            char[] cs = w.toCharArray();
            for (int p = 0; p < cs.length; p++) {
                char orig = cs[p];
                for (char c = 'a'; c <= 'z'; c++) {
                    cs[p] = c;
                    String x = new String(cs);
                    if (dict.remove(x)) {
                        dist.put(x, d + 1);
                        q.add(x);
                    }
                }
                cs[p] = orig;
            }
        }
        System.out.println(0);
    }
}

Solve Word Ladder online · All practice problems