package advanced.datastructure.graph.bfs.reachability.lc126_wordladder2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s)
 * from beginWord to endWord, such that:
 * Only one letter can be changed at a time
 * Each intermediate word must exist in the word list
 * For example,
 * Given: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"].
 * Return
 * [
 *  ["hit","hot","dot","dog","cog"],
 *  ["hit","hot","lot","log","cog"]
 * ]
 * Note: All words have the same length. All words contain only lowercase alphabetic characters.
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().findLadders("hit", "cog",
                new HashSet<>(Arrays.asList("hot", "dot", "dog", "lot", "log"))));
        System.out.println(new Solution().findLadders("red", "tax",
                new HashSet<>(Arrays.asList("ted","tex","red","tax","tad","den","rex","pee"))));
        System.out.println(new Solution().findLadders("hot", "dog",
                new HashSet<>(Arrays.asList("hot","dog"))));
    }

    // My 2AC
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        wordList.add(endWord);

        List<List<String>> result = new ArrayList<>();
        boolean isEnd = false;
        while (!queue.isEmpty() && !isEnd) {
            Set<String> visited = new HashSet<>();
            int size = queue.size();
            while (size-- > 0) {
                String ladder = queue.poll();
                String lastword = ladder.substring(ladder.length() - beginWord.length());
                if (lastword.equals(endWord)) {
                    result.add(Arrays.asList(ladder.split(",")));
                    isEnd = true;
                }
                if (isEnd) continue;

                for (int i = 0; i < lastword.length(); i++) {
                    char[] chars = lastword.toCharArray();
                    for (char c = 'a'; (chars[i] = c) <= 'z'; c++) {
                        //if (c == lastword.charAt(i)) continue;
                        String newword = new String(chars);
                        if (wordList.contains(newword)) {  // error: don't remove now, otherwise missing solution
                            queue.offer(ladder + "," + newword);
                            visited.add(newword);
                        }
                    }
                }
            }
            wordList.removeAll(visited);
        }
        return result;
    }

}

@@ -1329,16 +1329,1368 @@
 %0A    %7D%0A%0A
+    public List%3CList%3CString%3E%3E findLadders(String start, String end, Set%3CString%3E dict) %7B%0A        Queue%3CList%3CString%3E%3E q = new LinkedList%3C%3E();%0A        if (!start.isEmpty()) q.offer(Arrays.asList(start));%0A        dict.add(end);%0A%0A        List%3CList%3CString%3E%3E ret = new ArrayList%3C%3E();%0A        for (int i = 1; !q.isEmpty(); i++) %7B%0A            Set%3CString%3E vis = new HashSet%3C%3E();%0A            for (int j = q.size(); j %3E 0; j--) %7B%0A                List%3CString%3E path = q.poll();%0A                String word = path.get(path.size() - 1);%0A                if (end.equals(word)) ret.add(path);%0A                if (!ret.isEmpty()) continue;%0A%0A                char%5B%5D ch = word.toCharArray();%0A                for (int k = 0; k %3C ch.length; k++) %7B%0A                    for (char c = 'a'; c %3C= 'z'; c++) %7B%0A                        ch%5Bk%5D = c;%0A                        String nw = String.valueOf(ch);%0A                        if (dict.contains(nw)) %7B%0A                            List%3CString%3E np = new ArrayList%3C%3E(path);%0A                            np.add(nw);%0A                            q.offer(np);%0A                            vis.add(nw);%0A                        %7D%0A                    %7D%0A                    ch%5Bk%5D = word.charAt(k);%0A                %7D%0A            %7D%0A            dict.removeAll(vis); // remove at last to avoid missing out solution%0A        %7D%0A        return ret;%0A    %7D%0A%0A
     // M
@@ -2728,32 +2728,33 @@
 ng%3E%3E findLadders
+2
 (String beginWor

word ladder II