# Word Squares

This page explains Java solution to problem `Word Squares` using `Backtracking` algorithm.

## Problem Statement

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)`.

Example 1:

Output:
[
[ "wall",
"area",

[ "ball",
"area",
]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class WordSquares {
private HashMap<String, HashSet<String>> prefixMap;
private List<List<String>> res;
private String[] words;

public List<List<String>> wordSquares(String[] words) {
this.words = words;
this.prefixMap = new HashMap<>();
this.res = new ArrayList<>();

for(String word: words) {
for(int i = 0; i < word.length(); i++) {
String prefix = word.substring(0, i);
HashSet<String> set = prefixMap.getOrDefault(prefix, new HashSet<>());
prefixMap.put(prefix, set);
}
}
helper(0, new ArrayList<>());
return res;
}

private void helper(int row, List<String> wordList) {
else {
String prefix = "";
for(String word: wordList) prefix += word.charAt(row);

if(!prefixMap.containsKey(prefix)) return;

for(String prefixWord: prefixMap.get(prefix)) {
helper(row + 1, wordList);
wordList.remove(wordList.size() - 1);
}
}
}
}
``````

## Time Complexity

O(N * 26L) Where
N is total number words in an input array
L is length of single word
26 Alphabets a-z

## Space Complexity

O(N * L) Where
N is total number words in an input array
L is length of single word