425. Word Squares

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

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

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

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

301. Remove Invalid Parentheses

BFS

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

backtrack

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)