Example: Word Squares - rFronteddu/general_wiki GitHub Wiki

Problem Statement: Given a set of words, find all possible word squares. A word square is a grid of words, where each word is the same length as the number of rows/columns, and words are formed by reading horizontally and vertically.

Example: If the given words are ["area", "lead", "wall", "lady", "ball"], then one possible word square would be:

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

To solve this problem efficiently, you can use a backtracking approach combined with a trie data structure to prune the search space.

Here's how you can approach this problem:

  1. Build a Trie: Construct a trie from the given set of words. Each level of the trie represents a letter in the words.
  2. Backtracking: Perform a depth-first search (DFS) on the trie to build the word squares. At each step, try adding a word to the current square and check if the resulting square is valid. If it's valid, continue building the square. If not, backtrack and try a different word.
  3. Check Validity: At each step of the backtracking process, check if the partial word square formed so far is valid. For example, check if each word formed by reading the rows and columns matches a word in the trie.
  4. Stop Condition: Stop the backtracking process when you've formed a complete word square (i.e., when the number of words in the square equals the length of each word).
import java.util.*;

public class WordSquares {
    
    class TrieNode {
        List<String> words;
        TrieNode[] children;
        
        TrieNode() {
            words = new ArrayList<>();
            children = new TrieNode[26];
        }
    }
    
    TrieNode root;
    int wordLength;
    
    public List<List<String>> wordSquares(String[] words) {
        root = new TrieNode();
        wordLength = words[0].length();
        
        // Build the trie
        for (String word : words) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
                node.words.add(word);
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        List<String> square = new ArrayList<>();
        
        // Start the backtracking
        for (String word : words) {
            square.add(word);
            backtrack(square, 1, result);
            square.remove(0); // Remove the first word to try next starting word
        }
        
        return result;
    }
    
    private void backtrack(List<String> square, int row, List<List<String>> result) {
        if (row == wordLength) {
            result.add(new ArrayList<>(square));
            return;
        }
        
        StringBuilder prefixBuilder = new StringBuilder();
        for (String word : square) {
            prefixBuilder.append(word.charAt(row));
        }
        String prefix = prefixBuilder.toString();
        
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return; // No words with this prefix
            }
            node = node.children[index];
        }
        
        for (String word : node.words) {
            square.add(word);
            backtrack(square, row + 1, result);
            square.remove(square.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        WordSquares solution = new WordSquares();
        String[] words = {"area", "lead", "wall", "lady", "ball"};
        List<List<String>> squares = solution.wordSquares(words);
        for (List<String> square : squares) {
            for (String word : square) {
                System.out.println(word);
            }
            System.out.println();
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️