1848 · Word Search III
https://www.lintcode.com/problem/1848/
Hard
Description
Given a matrix of lower alphabets and a dictionary. Find maximum number of words in the dictionary that can be found in the matrix at the same time. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. One character only be used once in the matrix. No same word in dictionary
Example
Example 1:
Input：
["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]
Output：
2
Explanation：
d o a f
a g a i
d c a n
search in Matrix, you can find `dog` and `can` in the meantime.
Example 2:
Input：
["a"]，["b"]
Output：
0
Explanation：
a
search in Matrix，return 0.
Tags
- Hash Table
- Depth First Search/DFS
- Trie
算法
- DFS + Trie （HashMap应该也可）
算法思路
-
本题和word search II整体类似，只是最后要求的东西改变了，改为要求同时在整个棋盘上可以圈出的单词数量。采用和word search II一致的思路。
-
首先使用trie去预处理dict，用于表示前缀。然后从棋盘的起始点开始dfs，每当我们找到一个单词以后，我们继续在当前棋盘继续进行dfs，直到搜不到单词为止。
优化
- 我们可以在棋盘搜索的时候进行优化，当一个单词找到以后，下一个单词我们可以从上一个单词的起点的后面开始搜索。因此我们在dfs的过程中可以记录一下单词的起始点，这样用于下一次开始的枚举。
from typing import (
List,
)
class TrieNode:
def __init__(self, letter=""):
self.val = letter
self.is_end_of_word = False
self.children = dict()
class Trie:
def __init__(self):
self.root = TrieNode() # init root node []
def insert(self, word): # inser one word
currnode = self.root
for letter in word: # e.g. word is "abc"
if letter not in currnode.children:
currnode.children[letter] = TrieNode(letter) # [] -> {a}
currnode = currnode.children[letter] # make nextnode to be new currnode, to make [] -> {a} -> {b} in next forloop
currnode.is_end_of_word = True # last letter marked as end of word
class Solution:
"""
@param board: A list of lists of character
@param words: A list of string
@return: return the maximum nunber
"""
def word_search_i_i_i(self, board: List[List[str]], words: List[str]) -> int:
# write your code here
trie = Trie()
for word in words:
trie.insert(word)
rowleng = len(board)
colleng = len(board[0])
visited = [[False] * colleng for _ in range(rowleng)]
return self.traverse(board, 0, -1, rowleng, colleng, trie, visited)
def traverse(self, board, start_i, start_j, rowleng, colleng, trie, visited): # 这一部分单独搞出来是因为一个单词结束后查第二个单词时还要调用
word_count = 0
for i in range(start_i, rowleng):
start_j = start_j + 1 if start_i == i else 0 # 新单词从上一个单词的起点处的下一个cell开始；所以初始要传-1进来
for j in range(start_j, colleng):
if visited[i][j]: # true是那些cell属于已完成的前一个单词，现在已经在找连着的下一个单词
continue
currletter = board[i][j]
if currletter not in trie.root.children: # root is [], root.children all possible starting letters
continue # not any word starting lettter
visited[i][j] = True
# print("start: ", currletter)
word_count = max(word_count,
self.dfs(board, trie, trie.root.children[currletter], i, j, i, j, rowleng, colleng, visited)
)
visited[i][j] = False
return word_count
def dfs(self, board, trie, currnode, i, j, start_i, start_j, rowleng, colleng, visited):
word_count = 0
# print("currnode: ", currnode, currnode.val, currnode.children, currnode.is_end_of_word)
if currnode.is_end_of_word: # 一个单词结束 立刻开始下一个单词
currnode.is_end_of_word = False
# 开始下一个单词
word_count = self.traverse(board, start_i, start_j, rowleng, colleng, trie, visited) + 1
currnode.is_end_of_word = True
# 常规dfs部分
for offsetx, offsety in [[0,1], [0,-1], [1,0], [-1,0]]:
newx, newy = i + offsetx, j + offsety
if not (0 <= newx <= rowleng-1 and 0 <= newy <= colleng-1) or visited[newx][newy]:
continue
newletter = board[newx][newy]
# print("newletter: ", newletter, currnode, currnode.children.keys())
if newletter not in currnode.children:
continue #不是一个单词内部的字母
visited[newx][newy] = True
word_count = max(word_count,
self.dfs(board, trie, currnode.children[newletter],
newx, newy, start_i, start_j, rowleng, colleng, visited)
)
visited[newx][newy] = False
return word_count