当前位置:网站首页>Leetcode word search (backtracking method)
Leetcode word search (backtracking method)
2022-07-05 04:54:00 【Little light_】
subject
Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .
The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .
Example 1:
Input :board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output :true
Example 2:
Input :board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output :true
Example 3:
Input :board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output :false
Tips :
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word It consists of upper and lower case English letters onlysource : Power button (LeetCode)
link :https://leetcode.cn/problems/word-search
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas
Because I just did a maze problem not long ago , So after reading this question , I found it amazingly similar to walking through a maze , It's just that the conditions change when we take the next step . however , It still cost me 2 How close are you to 3 It took hours to write !, alas , Don't say the , It's still too much for me .
Get down to business ( Food can't be a reason for my laziness )
First , Whether it's maze walking or this problem , There must be a starting point , For this question , If you try one by one , That would be too time-consuming , So I first traverse the whole grid , Find the position of the letter that is the same as the first letter of the word you want to find :
start_pos_li = [] # Record the position of the first letter of the word word_set = set() # All letters in the table m, n = len(board), len(board[0]) for i in range(m): for j in range(n): word_set.add(board[i][j]) if board[i][j] == word[0]: start_pos_li.append((i, j))
The found letters are added to start_pos_li In this list , Easy to find in the future, directly start from these locations .
At the same time, I also set up a set word_set, Save all the letters appearing in the grid , Before the official search , You can make a simple judgment to quickly get the answer of some chestnuts :
for s in word: if s not in word_set: return False # As long as there is a letter not in the table, it returns False
As the code shows , Traverse the words you need to find , As long as there is a letter not in the set, it will be returned directly False.
Now let's start the formal search
1. First define a move rule :
# Move ( Four directions ) def move(self, x, y, direction): if direction == 1: return (x - 1, y) elif direction == 2: return (x + 1, y) elif direction == 3: return (x, y - 1) else: return (x, y + 1)
1 Represents moving up ,2 Represents moving down ,3 Represents shift left ,4 For shift right ; Here I take the horizontal axis as y Axis , Vertical axis as x Axis , therefore When moving up and down x Axis found changes , When moving left and right y The axis changes .
2. Begin to walk tentatively
a. Define a “ Stack ” To save the path
path = [start] # Record the path
In fact, here is a list , But only using append() and pop() Method , Then it behaves like a stack .
b. Define a list to save the direction of each grid
visit_li = [[set() for j in range(n)] for i in range(m)] # Record the direction from the current position to the next step
Here I use a set to store the direction of each grid , A grid can store up to four directions , That is, up and down, around ; Unlike going through a maze , In maze walking, it is represented by two values :0 Represents that the current grid has not passed ,1 Represents that the current grid has left ; Because here is a word , It requires a continuous sequence , The current grid may not come from this direction , But you can come from the other direction .( That is, take the grid from different directions , The sequences obtained are all different )
c. Probe + to flash back
# Start with the initial letter for start in start_pos_li: path = [start] # Record the path visit_li = [[set() for j in range(n)] for i in range(m)] # Record the direction from the current position to the next step while path: # print(path) if len(path) == len(word): return True # As long as the path is the same as the length of the word, it means that you are finished cur_pos = path[-1] # The current position (m,n) for step in range(4): # Explore in four directions next_pos = self.move(*cur_pos, step) # next step if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][ cur_pos[1]] and next_pos not in set(path): # The next step can be taken without going through if board[next_pos[0]][next_pos[1]] == word[len(path)]: # The letters in the next position are the same as those required path.append(next_pos) # Just move to the next step visit_li[cur_pos[0]][cur_pos[1]].add(step) # Mark that the position has passed break else: visit_li[cur_pos[0]][cur_pos[1]].add(step) # Mark that this direction won't work else: x, y = path.pop() # If you can't walk in four directions, go back visit_li[x][y] = set() # At the same time, clear the direction that the position has passed
From the beginning , Test whether the four directions can go in turn , If the walkable point is updated to the current position , And then continue to test , If to a certain point , None of the four directions will work , Then go back , Go back to the previous step ; Continue the direction you didn't finish last time , Take the following chestnut as an example :
Source code
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
'''
It's like going through a maze , Set up 4 Two directions of movement , At the same time, mark the places you have passed
'''
start_pos_li = [] # Record the position of the first letter of the word
word_set = set() # All letters in the table
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
word_set.add(board[i][j])
if board[i][j] == word[0]:
start_pos_li.append((i, j))
for s in word:
if s not in word_set: return False # As long as there is a letter not in the table, it returns False
# Start with the initial letter
for start in start_pos_li:
path = [start] # Record the path
visit_li = [[set() for j in range(n)] for i in range(m)] # Record the direction from the current position to the next step
while path:
# print(path)
if len(path) == len(word): return True # As long as the path is the same as the length of the word, it means that you are finished
cur_pos = path[-1] # The current position (m,n)
for step in range(4): # Explore in four directions
next_pos = self.move(*cur_pos, step) # next step
if 0 <= next_pos[0] < m and 0 <= next_pos[1] < n and step not in visit_li[cur_pos[0]][
cur_pos[1]] and next_pos not in set(path): # The next step can be taken without going through
if board[next_pos[0]][next_pos[1]] == word[len(path)]: # The letters in the next position are the same as those required
path.append(next_pos) # Just move to the next step
visit_li[cur_pos[0]][cur_pos[1]].add(step) # Mark that the position has passed
break
else:
visit_li[cur_pos[0]][cur_pos[1]].add(step) # Mark that this direction won't work
else:
x, y = path.pop() # If you can't walk in four directions, go back
visit_li[x][y] = set() # At the same time, clear the direction that the position has passed
# print('*' * 100)
return False
# Move ( Four directions )
def move(self, x, y, direction):
if direction == 1:
return (x - 1, y)
elif direction == 2:
return (x + 1, y)
elif direction == 3:
return (x, y - 1)
else:
return (x, y + 1)
Through screenshots
Synchronous update in personal blog system :LeetCode Word search ( To solve by backtracking )
边栏推荐
- AutoCAD - Document Management
- The 22nd Spring Festival Gala, an immersive stage for the yuan universe to shine into reality
- The difference between bundle, chunk and module
- 【acwing】240. food chain
- The principle of attention mechanism and its application in seq2seq (bahadanau attention)
- [crampon game] MC tutorial - first day of survival
- AutoCAD - workspace settings
- Flutter 小技巧之 ListView 和 PageView 的各种花式嵌套
- [Business Research Report] top ten trends of science and technology and it in 2022 - with download link
- 3dsmax scanning function point connection drawing connection line
猜你喜欢
AutoCAD - continuous annotation
An article takes you to thoroughly understand descriptors
3dsmax scanning function point connection drawing connection line
[groovy] closure (closure parameter list rule | default parameter list | do not receive parameters | receive custom parameters)
[crampon game] MC tutorial - first day of survival
【Leetcode】1352. 最后 K 个数的乘积
LeetCode之单词搜索(回溯法求解)
【acwing】240. food chain
How should programmers learn mathematics
Flutter 小技巧之 ListView 和 PageView 的各种花式嵌套
随机推荐
Detailed explanation of the ranking of the best universities
[Business Research Report] Research Report on male consumption trends in other economic times -- with download link
AutoCAD - full screen display
Scope of package class package
2022 thinking of Mathematical Modeling B problem of American college students / analysis of 2022 American competition B problem
Mode in BST (binary tree & Notes on question brushing)
English topic assignment (27)
PR first time
2022 U.S. college students' mathematical modeling e problem ideas / 2022 U.S. game e problem analysis
[groovy] closure closure (customize closure parameters | customize a single closure parameter | customize multiple closure parameters | specify the default value of closure parameters)
Special information | real estate and office buildings - 22.1.9
MD5 bypass
A survey of automatic speech recognition (ASR) research
Flink cluster configuration
中国聚氨酯硬泡市场调研与投资预测报告(2022版)
54. Spiral matrix & 59 Spiral matrix II ●●
Redis 排查大 key 的4种方法,优化必备
3dsmax scanning function point connection drawing connection line
Emlog blog theme template source code simple good-looking responsive
GameObject class and transform class of unity