動機

原來lru_cache搭配dfs可以達到判有沒有visited的效果!!

Problem

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

Example 1:

Input: board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words = [oath,pea,eat,rain]Output: [eat,oath]

Example 2:

Input: board = [[a,b],[c,d]], words = [abcb]Output: []

 

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Sol

都是dfs+trie去看有沒有單字，不過要注意的是像[app,apple]不能在看到app就停下來

class Solution:
    def buildTrie(self):
        self.trie = [None, {}]
        for (i,w) in enumerate(self.ws):
            tmp = self.trie
            for c in w:
                if c not in tmp[1]:
                    tmp[1][c] = [None, {}]
                tmp = tmp[1][c]
            tmp[0] = i
    def hasChar(self,trie,c):
        if c in trie[1]:
            return trie[1][c]
        else:
            return [None, {}]
    def dfs(self,i,j, trie, pos):
        if i < 0 or i >= len(self.b) or j < 0 or j >= len(self.b[0]):
            return []
        else:
            trie2 = self.hasChar(trie,self.b[i][j])
            ret = [] if trie2[0] is None else [self.ws[trie2[0]]]
            if trie2[1]:
                dirs = [x for x in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] if x not in pos]
                for p in dirs:
                    ret += self.dfs(p[0],p[1],trie2,pos+[p])
            return ret
    def findWords(self, board: List[List[str]], ws: List[str]) -> List[str]:
        self.ws = ws
        self.buildTrie()
        #print(self.trie)
        self.b = board
        ret = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                ret += self.dfs(i,j,self.trie,[(i,j)])
        return list(set(ret))

Sol2: lru_cache與標記來標visited

為了避免找重複

  • (ret): 改trie來看有沒有看過這個單字
  • (dfs的表): 走過的路就mark掉
    • backtracking常用技巧: 走過的路就mark掉，其實與改trie一樣
  • (列舉點): lru_cache避免dfs再走一次
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self, word):
        node = self.root
        for letter in word:
            node = node.children[letter]
        node.isWord = True

class Solution:
    def buildTrie(self):
        for word in self.ws:
            self.trie.add(word)
    @lru_cache(None)
    def dfs(self,i,j, trie,cur):
        if trie.isWord:
            self.ret.append(cur)
            trie.isWord = False
        if 0 <= i < len(self.b) and 0 <= j < len(self.b[0]):
            if self.b[i][j] != '#':
                dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
                now = self.b[i][j]
                tmpTrie = trie.children.get(now)
                if tmpTrie:
                    tmpCur = cur+now
                    self.b[i][j] = '#'
                    for (x,y) in dirs:
                        self.dfs(i+x,j+y,tmpTrie,tmpCur)
                    self.b[i][j] = now
    def findWords(self, board: List[List[str]], ws: List[str]) -> List[str]:
        self.ws = ws
        self.trie = Trie()
        self.buildTrie()
        #print(self.trie)
        self.b = board
        self.ret = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(i,j,self.trie.root,"")
        return self.ret