# 给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
# 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
# 同一个单元格内的字母在一个单词中不允许被重复使用。
# 示例:
# 输入:
# words = ["oath","pea","eat","rain"] and board =
# [
# ['o','a','a','n'],
# ['e','t','a','e'],
# ['i','h','k','r'],
# ['i','f','l','v']
# ]
# 输出: ["eat","oath"]
# 说明:
# 你可以假设所有输入都由小写字母 a-z 组成。
# 提示:
# 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯?
# 如果当前单词不存在于所有单词的前缀中,则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作?散列表是否可行?为什么?
# 前缀树如何?如果你想学习如何实现一个基本的前缀树,请先查看这个问题: 实现Trie(前缀树)。
import random
words = ["oath", "pea", "eat", "rain"]
board = [
['o', 'a', 'a', 'n'],
['e', 't', 'a', 'e'],
['i', 'h', 'k', 'r'],
['i', 'f', 'l', 'v']
]
# 判断附近有单词能够和之前的组成同一个单词不
def is_same_word(x, y, word, i):
if i >=len(word):
return True
# x,y是当前单词在board的坐标,只要有一个相同就递归进去
if x + 1 < board.__len__() and y < board.__len__():
if board[x + 1][ y] == word[i]:
return is_same_word(x + 1, y, word, i + 1)
if y+1<board.__len__() and x<board.__len__():
if board[x][y + 1] == word[i]:
return is_same_word(x, y + 1, word, i + 1)
if x - 1 < board.__len__() and y < board.__len__():
if board[x - 1][ y] == word[i]:
return is_same_word(x - 1, y, word, i + 1)
if x < board.__len__() and y - 1 < board.__len__():
if board[x][ y - 1] == word[i]:
return is_same_word(x, y - 1, word, i + 1)
return False
#满足条件的word的集合
words_ok = []
# 遍历找到words中的每个单词
for word in words:
# 然后在Board中遍历 与word首字母相同的
for board_x,board_x_item in enumerate(board):
for board_y,board_y_item in enumerate(board_x_item):
if board[board_x][board_y] == word[0]:
if is_same_word(board_x,board_y,word,1):
words_ok.append(word)
print(words_ok)
单词搜索 II
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 212. 单词搜索 II 给定一个二维网格 **board **和一个字典中的单词列表 words,找出所有同时在...
- 第一版先来个爆搜的,对于每一个单词,先找找有没有跟第一个字母相等的,找到后开始向四周找这个单词。后来超时。第二版,...
- 近日,由张介公博士主讲、喜马拉雅电台协助发行,全国各地的学子纷纷号召支持下,集科学教育记忆题材于一体的大型史诗教育...