> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/backtracking/425-word-squares.md).

# 425    Word Squares

## 425. [Word Squares](https://leetcode.com/problems/word-squares/description/)

## 1. Question

Given a set of words**(without duplicates)**, find all [word squares](https://en.wikipedia.org/wiki/Word_square) 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 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
```

## 2. Implementation

**(1) Backtracking**

```java
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