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).
For example, the word sequence
["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.b a l l
a r e a
l e a d
l a d y
Example
Given a set ["area","lead","wall","lady","ball"]
return [["wall","area","lead","lady"],["ball","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Given a set ["abat","baba","atan","atal"]
return [["baba","abat","baba","atan"],["baba","abat","baba","atal"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Notice
- There are at least 1 and at most 1000 words.
- All words will have the exact same length.
- Word length is at least 1 and at most 5.
- Each word contains only lowercase English alphabet
a-z.
For a naive solution, for each row, we can have at most n possbile choices, where n is the number of words. For the word length with m, the toal time is n^m. For each possible board, we need additional n * m time to check if it's a squre or not. So the total time complexity is O(n^m * n * m).
Do we have a better solution? We can actually use a trie to look up candidates quickly. For the first row, we can have n possibilities. For the second row, we have 1st character set, for the second, we have 1st and 2nd character set, for the third row, we have first, second and third characters set, etc..
So the idea is for each prefix, we go to the trie and get all the words with that prefix. Then try to use DFS to go through all probabilities.
Code (Java):
public class Solution {
/*
* @param words: a set of words without duplicates
* @return: all word squares
*/
public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if (words == null || words.length == 0) {
return ans;
}
Trie trie = new Trie();
for (String word : words) {
trie.add(word);
}
int len = words[0].length();
for (String word : words) {
List<String> curr = new ArrayList<>();
curr.add(word);
wordSquaresHelper(1, len, curr, trie, ans);
curr.remove(curr.size() - 1);
}
return ans;
}
private void wordSquaresHelper(int start, int len, List<String> curr, Trie trie, List<List<String>> ans) {
if (start >= len) {
ans.add(new ArrayList<>(curr));
return;
}
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < start; i++) {
prefix.append(curr.get(i).charAt(start));
}
List<String> candidates = trie.getPrefixStrs(prefix.toString());
for (String candidate : candidates) {
System.out.println("candidate: " + candidate);
}
for (String candidate : candidates) {
curr.add(candidate);
wordSquaresHelper(start + 1, len, curr, trie, ans);
curr.remove(curr.size() - 1);
}
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void add(String s) {
TrieNode p = root;
for (char c : s.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new TrieNode();
}
p = p.children[c - 'a'];
}
p.leaf = true;
}
public List<String> getPrefixStrs(String prefix) {
TrieNode p = root;
List<String> ans = new ArrayList<>();
for (char c : prefix.toCharArray()) {
if (p.children[c - 'a'] == null) {
return ans;
}
p = p.children[c - 'a'];
}
StringBuilder sb = new StringBuilder(prefix);
getPrefixHelper(p, sb, ans);
return ans;
}
private void getPrefixHelper(TrieNode p, StringBuilder curr, List<String> ans) {
if (p == null) {
return;
}
if (p.leaf) {
ans.add(curr.toString());
return;
}
for (int i = 0; i < 26; i++) {
if (p.children[i] != null) {
curr.append((char) (i + 'a'));
getPrefixHelper(p.children[i], curr, ans);
curr.deleteCharAt(curr.length() - 1);
}
}
}
}
class TrieNode {
TrieNode[] children;
boolean leaf;
public TrieNode() {
children = new TrieNode[26];
leaf = false;
}
}
An even better solution:
To find all the words with the prefix is an expensive operation. A better solution is to cache the word in all nodes.
Code (Java):
/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/
public class Solution {
class TrieNode {
List<String> startWith;
TrieNode[] children;
TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}
class Trie {
TrieNode root;
Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur.children[idx].startWith.add(w);
cur = cur.children[idx];
}
}
}
List<String> findByPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
return ans;
cur = cur.children[idx];
}
ans.addAll(cur.startWith);
return ans;
}
}
public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if (words == null || words.length == 0)
return ans;
int len = words[0].length();
Trie trie = new Trie(words);
List<String> ansBuilder = new ArrayList<>();
for (String w : words) {
ansBuilder.add(w);
search(len, trie, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
return ans;
}
private void search(int len, Trie tr, List<List<String>> ans,
List<String> ansBuilder) {
if (ansBuilder.size() == len) {
ans.add(new ArrayList<>(ansBuilder));
return;
}
int idx = ansBuilder.size();
StringBuilder prefixBuilder = new StringBuilder();
for (String s : ansBuilder)
prefixBuilder.append(s.charAt(idx));
List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
for (String sw : startWith) {
ansBuilder.add(sw);
search(len, tr, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
}
}
No comments:
Post a Comment