package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 425. Word Squares
 *
 * Given a set of words (without duplicates), find all word squares you can build from them.

 A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

 For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

 b a l l
 a r e a
 l e a d
 l a d y

 Note:

 There are at least 1 and at most 1000 words.
 All words will have the exact same length.
 Word length is at least 1 and at most 5.
 Each word contains only lowercase English alphabet a-z.

 Example 1:

 Input:
 ["area","lead","wall","lady","ball"]

 Output:
 [
 [ "wall",
 "area",
 "lead",
 "lady"
 ],
 [ "ball",
 "area",
 "lead",
 "lady"
 ]
 ]

 Explanation:
 The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).


 Example 2:

 Input:
 ["abat","baba","atan","atal"]

 Output:
 [
 [ "baba",
 "abat",
 "baba",
 "atan"
 ],
 [ "baba",
 "abat",
 "baba",
 "atal"
 ]
 ]

 Explanation:
 The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
 */
public class _425 {

    public static class Solution1 {
        /**
         * Credit: https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16/2
         */

        class TrieNode {
            List<String> startWith;
            TrieNode[] children;

            TrieNode() {
                startWith = new ArrayList<>();
                children = new TrieNode[26];
            }
        }

        class Trie {
            TrieNode root;

            Trie(String[] words) {
                root = new TrieNode();
                for (String word : words) {
                    TrieNode cur = root;
                    for (char ch : word.toCharArray()) {
                        int index = ch - 'a';
                        if (cur.children[index] == null) {
                            cur.children[index] = new TrieNode();
                        }
                        cur.children[index].startWith.add(word);
                        cur = cur.children[index];
                    }
                }
            }

            List<String> findByPrefix(String prefix) {
                List<String> ans = new ArrayList<>();
                TrieNode cur = root;
                for (char ch : prefix.toCharArray()) {
                    int index = ch - 'a';
                    if (cur.children[index] == null) {
                        return ans;
                    }

                    cur = cur.children[index];
                }
                ans.addAll(cur.startWith);
                return ans;
            }
        }

        public List<List<String>> wordSquares(String[] words) {
            List<List<String>> ans = new ArrayList<>();
            if (words == null || words.length == 0) {
                return ans;
            }
            int len = words[0].length();
            Trie trie = new Trie(words);
            List<String> ansBuilder = new ArrayList<>();
            for (String w : words) {
                ansBuilder.add(w);
                search(len, trie, ans, ansBuilder);
                ansBuilder.remove(ansBuilder.size() - 1);
            }

            return ans;
        }

        private void search(int len, Trie trie, List<List<String>> ans,
                            List<String> ansBuilder) {
            if (ansBuilder.size() == len) {
                ans.add(new ArrayList<>(ansBuilder));
                return;
            }

            int idx = ansBuilder.size();
            StringBuilder prefixBuilder = new StringBuilder();
            for (String s : ansBuilder) {
                prefixBuilder.append(s.charAt(idx));
            }
            List<String> startWith = trie.findByPrefix(prefixBuilder.toString());
            for (String sw : startWith) {
                ansBuilder.add(sw);
                search(len, trie, ans, ansBuilder);
                ansBuilder.remove(ansBuilder.size() - 1);
            }
        }
    }

}


@@ -85,1264 +85,8 @@
 t;%0A%0A
-/**%0A * 425. Word Squares%0A *%0A * Given a set of words (without duplicates), find all word squares you can build from them.%0A%0A A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 %E2%89%A4 k %3C max(numRows, numColumns).%0A%0A For example, the word sequence %5B%22ball%22,%22area%22,%22lead%22,%22lady%22%5D forms a word square because each word reads the same both horizontally and vertically.%0A%0A b a l l%0A a r e a%0A l e a d%0A l a d y%0A%0A Note:%0A%0A There are at least 1 and at most 1000 words.%0A All words will have the exact same length.%0A Word length is at least 1 and at most 5.%0A Each word contains only lowercase English alphabet a-z.%0A%0A Example 1:%0A%0A Input:%0A %5B%22area%22,%22lead%22,%22wall%22,%22lady%22,%22ball%22%5D%0A%0A Output:%0A %5B%0A %5B %22wall%22,%0A %22area%22,%0A %22lead%22,%0A %22lady%22%0A %5D,%0A %5B %22ball%22,%0A %22area%22,%0A %22lead%22,%0A %22lady%22%0A %5D%0A %5D%0A%0A Explanation:%0A The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).%0A%0A%0A Example 2:%0A%0A Input:%0A %5B%22abat%22,%22baba%22,%22atan%22,%22atal%22%5D%0A%0A Output:%0A %5B%0A %5B %22baba%22,%0A %22abat%22,%0A %22baba%22,%0A %22atan%22%0A %5D,%0A %5B %22baba%22,%0A %22abat%22,%0A %22baba%22,%0A %22atal%22%0A %5D%0A %5D%0A%0A Explanation:%0A The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).%0A */%0A
 publ

refactor 425