425 Word Squares

425. Word Squares

1. Question

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 thekthrow 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:

1. There are at least 1 and at most 1000 words.

2. All words will have the exact same length.

3. Word length is at least 1 and at most 5.

4. Each word contains only lowercase English alphabeta-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

2. Implementation

(1) Backtracking

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new ArrayList();

        if (words == null || words.length == 0) {
            return res;
        }

        Trie trie = new Trie();

        for (String word : words) {
            trie.insert(word);
        }

        List<String> square = null;
        int len = words[0].length();

        for (String word : words) {
            square = new ArrayList();
            square.add(word);
            searchSquare(len, trie, square, res);
        }
        return res;
    }

    public void searchSquare(int len, Trie trie, List<String> square, List<List<String>> res) {
        if (square.size() == len) {
            res.add(new ArrayList(square));
            return;
        }

        int index = square.size();

        StringBuilder prefix = new StringBuilder();

        for (String word : square) {
            prefix.append(word.charAt(index));
        }

        List<String> words = trie.searchPrefix(prefix.toString());

        if (words == null) {
            return;
        }

        for (String word : words) {
            square.add(word);
            searchSquare(len, trie, square, res);
            square.remove(square.size() - 1);
        }
    }

    class TrieNode {
        char val;
        boolean isWord;
        List<String> words;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            words = new ArrayList();
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';

                if (curNode.childNode[index] == null) {
                    curNode.childNode[index] = new TrieNode(c);
                }
                curNode.childNode[index].words.add(word);
                curNode = curNode.childNode[index];
            }
            curNode.isWord = true;
        }

        public List<String> searchPrefix(String word) {
            if (word == null || word.length() == 0) {
                return null;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';

                if (curNode.childNode[index] == null) {
                    return null;
                }
                curNode = curNode.childNode[index];
            }
            return curNode.words;
        }
    }
}

3. Time & Space Complexity