美文网首页
Python 键树记录—LeetCode(word-search

Python 键树记录—LeetCode(word-search

作者: 掉了西红柿皮_Kee | 来源:发表于2020-05-31 10:31 被阅读0次

I found myself not as enthusiastic as before.20200531


class Trie(object):
    """docstring for Trie"""
    def __init__(self):
        super(Trie, self).__init__()
        self.root = {}
        self.end_of_word = '#'
    
    def insert(self, word):
        node = self.root
        for char in word:
            # setdefault() 和 get() 类似, 如果键不存在,将会添加键并将值设为默认值。
            # dict.setdefault(key, default=None)
            node = node.setdefault(char,{})
        node[self.end_of_word] = self.end_of_word

    def search(self, word):
        node = self.root
        for char in node:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def start_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

题目描述:
https://leetcode-cn.com/problems/word-search-ii/

def findWords(board, words):

    res = set()
    rows = len(board)
    cols = len(board[0])

    # create trie
    root = {}
    for word in words:
        node = root
        for char in word:
            node = node.setdefault(char, {})
        node['#'] = '#'


    # dfs
    def dfs(i, j, board, cur_word, cur_dic):
        char = board[i][j]
        if char not in cur_dic:
            return
        cur_word += char
        cur_dic = cur_dic[char]

        # terminate condition
        if '#' in cur_dic:
            res.add(cur_word)
        # current deal
        tmp, board[i][j] = board[i][j],'0'
        # drill down
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            i_ = i + dx
            j_ = j + dy
            if 0 <= i_< rows and 0<=j_<cols and board[i_][j_]!='0':
                dfs(i_, j_, board, cur_word, cur_dic)
        # recover
        board[i][j] = tmp


    for i in range(rows):
        for j in range(cols):
            if board[i][j] not in root:
                continue
            dfs(i, j, board, '', root)
        
    return list(res)

结果生成过程:
root示意图

{
  'o': {
    'a': {
      't': {
        'h': {
          '#': '#'
        }
      }
    }
  },
  'p': {
    'e': {
      'a': {
        '#': '#'
      }
    }
  },
  'e': {
    'a': {
      't': {
        '#': '#'
      }
    }
  },
  'r': {
    'a': {
      'i': {
        'n': {
          '#': '#'
        }
      }
    }
  }
}
root.png
Done

相关文章

网友评论

      本文标题:Python 键树记录—LeetCode(word-search

      本文链接:https://www.haomeiwen.com/subject/eojlzhtx.html