# 425. Word Squares

{% embed url="<https://leetcode.com/problems/word-squares/>" %}

只能想到用`deque`来做`BFS`，拿首字母做了`hash map`来优化，险险过。

找新词 w 时候的判断是：`w[k] == wordsquare[k][d]`，`d`是已经找到的词的数量，其实就是维护整个word square 内部的 index 对称。

参考Q301的思路，也可以改写成 `backtrack` 的形式。但只要找新词的判断过程不变，总的时间复杂度还是近似的。

{% content-ref url="301.-remove-invalid-parentheses" %}
[301.-remove-invalid-parentheses](https://xuqiangwen1994.gitbook.io/practice/301.-remove-invalid-parentheses)
{% endcontent-ref %}

{% tabs %}
{% tab title="BFS" %}

```python
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        res = []
        n, l = len(words), len(words[0])
        
        init = collections.defaultdict(list)
        for w in words: init[w[0]].append(w)
        
        for i in words:
            q = collections.deque([[i]])
            while q:
                ws = q.popleft()
                d = len(ws)
                if d == l: 
                    res.append(ws)
                    continue
                for w in init[ws[0][d]]:
                    fit = True
                    for k in range(d):
                        if w[k] != ws[k][d]:
                            fit = False
                            break
                    if fit:
                        q.append(ws+[w])
                        #print(q)
                    
        return res
```

{% endtab %}

{% tab title="backtrack" %}

```python
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:    
        res = []
        init = collections.defaultdict(list)
        for w in words: init[w[0]].append(w)
        for w in words: self.backtrack([w], res, init)
        return res
    
    
    def backtrack(self, ws, res, init):
        d = len(ws)
        if d == len(ws[0]):
            res.append(ws)
            return 
        for w in init[ws[0][d]]:
            fit = True
            for k in range(d):
                if w[k] != ws[k][d]:
                    fit = False
                    break
            if fit:
                self.backtrack(ws+[w], res, init)
```

{% endtab %}
{% endtabs %}
