Word Ladder II

Word Ladderと同じ入力に対し、最短距離の複数パスを配列として返す問題。BFSで各ノードへの最短距離を探し、DFSでEnd Nodeへの最短パスを作成することで解くことができる。

use std::collections::{HashMap, HashSet, VecDeque};

#[derive(Default)]
struct Graph {
    neighbors: HashMap<String, HashSet<String>>,
    distance: HashMap<String, usize>,
    end: String,
    stack: Vec<String>,
    output: Vec<Vec<String>>,
}

impl Graph {
    fn dfs(&mut self, word: &str) {
        self.stack.push(word.to_string());

        if word == self.end {
            self.output.push(self.stack.clone());
            self.stack.pop();
            return;
        }

        let neighbors = self.neighbors.get(word).cloned();
        if let Some(neighbors) = neighbors {
            for neighbor in neighbors.iter() {
                if self.distance[neighbor] == self.distance[word] + 1 {
                    self.dfs(neighbor);
                }
            }
        }

        self.stack.pop();
    }
}

pub fn find_ladders(
    begin_word: String,
    end_word: String,
    word_list: Vec<String>,
) -> Vec<Vec<String>> {
    let mut word_dict: HashMap<String, Vec<String>> = HashMap::new();

    for word in word_list.into_iter() {
        for i in 0..word.len() {
            let new_word = [&word[..i], "*", &word[i + 1..]].join("");
            word_dict.entry(new_word).or_default().push(word.clone());
        }
    }

    let mut queue = VecDeque::new();
    queue.push_back((begin_word.clone(), 0));
    let mut visited = HashSet::new();
    visited.insert(begin_word.clone());
    let mut graph: Graph = Default::default();
    graph.end = end_word;

    // Run BFS to find minimum distance to each node
    while let Some((word, depth)) = queue.pop_front() {
        graph.distance.insert(word.clone(), depth);
        for i in 0..word.len() {
            let new_word = [&word[..i], "*", &word[i + 1..]].join("");
            if let Some(matched_words) = word_dict.get(&new_word) {
                for matched in matched_words.iter() {
                    graph
                        .neighbors
                        .entry(word.clone())
                        .or_default()
                        .insert(matched.clone());
                    graph
                        .neighbors
                        .entry(matched.clone())
                        .or_default()
                        .insert(word.clone());

                    if !visited.contains(matched) {
                        queue.push_back((matched.clone(), depth + 1));
                        visited.insert(matched.clone());
                    }
                }
            }
        }
    }

    // Run DFS to find multiple path to end node
    graph.dfs(&begin_word);
    graph.output
}

計算量はWord Ladderと同じくO(M² * N)