This page explains Java solution to problem Word Squares
using Backtracking
algorithm.
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)
.
Input: ["area","lead","wall","lady","ball"]
Output:
[
[ "wall",
"area",
"lead",
"lady"],
[ "ball",
"area",
"lead",
"lady"]
]
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);
}
}
}
}
O(N * 26L) Where
N is total number words in an input array
L is length of single word
26 Alphabets a-z
O(N * L) Where
N is total number words in an input array
L is length of single word