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:

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

      [ "ball",


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) {
        if(row == words[0].length()) res.add(new ArrayList<>(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