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"]
Output:
[
      [ "wall",
        "area",
        "lead",
        "lady"],

      [ "ball",
        "area",
        "lead",
        "lady"]
]

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<>());
                set.add(word);
                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)) {
                wordList.add(prefixWord);
                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