Word Square

422 Valid Word Square

Given a sequence of words, check whether it forms a valid word square.

A sequence of words forms a valid word square if the kth row and column read the exact same string

public boolean validWordSquare(List<String> words) {
   for(int i=0; i<words.size(); i++){
       for(int j=0; j<words.get(i).length(); j++){
           if(j>=words.size() || 
              i>= words.get(j).length() || 
              words.get(i).charAt(j) != words.get(j).charAt(i))
               return false;
       }
   }
    return true;
}

425 Word Square II

Given a set of words (without duplicates), find all word squares you can build from them.

• Build a trie, record the prefix string list in every node

• search the word by word square rule

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.prefixList = []

        
class Trie:
    def __init__(self, words):
        self.root = TrieNode()
        for word in words:
            node = self.root
            for c in word:
                node = node.children[c]
                node.prefixList.append(word)
                
    def serachPrefixWord(self, prefix):
        node = self.root
        for c in prefix:
            node = node.children[c]
            
        return node.prefixList
    

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        if not words: return []
        
        self.trie = Trie(words)
        
        self.s = set(words)
        self.ans = []
        
        for word in words:
            square = [word]
            self.backtrack(square, 1)
            
        return self.ans
            
        
    def backtrack(self, square, idx):
        if idx == len(square[0]):
            self.ans.append(square.copy())
            return
        
        # prefix 是利用 square 的 column 建成
        prefix = ''.join(word[idx] for word in square)
        
        # for cand in self.getWords(prefix):
        for cand in self.trie.serachPrefixWord(prefix):
            square.append(cand)
            self.backtrack(square, idx+1)
            square.pop()
        
    
#     def getWords(self, prefix):
#         return [word for word in self.s if word.startswith(prefix)]