一开始的深度优先搜索 没有注意到题目要求的是最小序列 应当直接判断出是BFS class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 #回溯法 尝试出所有的可能 找到可以转换的单词列表 记得 从a-》 b 之后要删除a 然后遍历 继续 max_len = len(wordList) str_len = len(endWord) res1, res2 = [], []
def findNextWord(last, wordList):
#理论上 已经删除了和last相等的元素 最多只有n-1个字母相等 找到相似的str 只有一个字母不同 注意要求的是顺序变化
res = []
for item in wordList:
count = 0
for j in range(str_len):
if last[j] != item[j]:
count += 1
if count <= 1:
res.append(item)
return res
def recursion(tmp_res, tmp_len, tmp_list, lastWord, res1, res2):
tmp = findNextWord(lastWord, wordList)
#print(lastWord, tmp)
if endWord in tmp:
tmp_res.append(endWord)
tmp_len+=1
res1.append(tmp_len)
res2.append(tmp_res)
return
for item in tmp:
#wordlist删除刚才的word
wordList.remove(item)
recursion(tmp_res+[item], tmp_len+1, wordList, item, res1, res2)
wordList.append(item)
recursion([beginWord], 1, wordList, beginWord, res1, res2)
#记得如果找不到的情况 如何分析
#print(res1)
#print(res2)
if not res1:
return 0
return min(res1)
#出现了超时 用的dfs会出现超时问题 用BFS（广度优先搜索）
修改之后的BFS 还是会超时 class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 wordList = set(wordList) #回溯法 尝试出所有的可能 找到可以转换的单词列表 记得 从a-》 b 之后要删除a 然后遍历 继续 max_len = len(wordList) str_len = len(endWord) res1, res2 = [], [] queue = [beginWord] cur_len = 1
def findNextWord(last, wordList):
#理论上 已经删除了和last相等的元素 最多只有n-1个字母相等 找到相似的str 只有一个字母不同 注意要求的是顺序变化
res = []
for item in wordList:
count = 0
for j in range(str_len):
if last[j] != item[j]:
count += 1
if count <= 1:
res.append(item)
return res
while queue:
l = len(queue)
cur_len += 1
for _ in range(l):
cur = queue.pop(0)
#该树中无重复元素 即 广度搜寻出来的都可以删除 因为题目要求找的是最短序列长度
if cur in wordList:
wordList.remove(cur)
tmp = findNextWord(cur, wordList)
print(cur, tmp)
if endWord in tmp:
return cur_len
for item in tmp:
queue.append(item)
return 0
使用 自己遍历生成所有可能的下一个next字符串 再判断是否再字典里 还是超时 class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 wordList = set(wordList) #回溯法 尝试出所有的可能 找到可以转换的单词列表 记得 从a-》 b 之后要删除a 然后遍历 继续 max_len = len(wordList) str_len = len(endWord) queue = [beginWord] cur_len = 1
while queue:
l = len(queue)
for _ in range(l):
cur = queue.pop(0)
if cur == endWord:
return cur_len
#该树中无重复元素 即 广度搜寻出来的都可以删除 因为题目要求找的是最短序列长度
if cur in wordList:
wordList.remove(cur)
for i in range(str_len):
for a in range(97, 123):
w = cur[:i] + chr(a) + cur[i+1:]
if w in wordList:
queue.append(w)
cur_len += 1
return 0
最终修改版本 主要改动是变成了双向BFS 选择了分支小的那一侧来进行BFS遍历 即 class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 wordList = set(wordList) str_len = len(endWord)
head = {beginWord}
tail = {endWord}
tmp = list('abcdefghijklmnopqrstuvwxyz')
cur_len = 1
while head:
#关键点 在这 就是交换了首位逼近 通过首尾来互相逼近
if len(head) > len(tail):
head, tail = tail, head
next = set()
for cur in head :
for i in range(str_len):
for j in tmp:
#用这种方式来直接生成下一个next的内容
word = cur[:i] + j + cur[i+1:]
if word in tail:
return cur_len+1
if word in wordList:
next.add(word)
wordList.remove(word)
head = next
cur_len += 1
return 0
class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ if not board: return m = len(board) n = len(board[0]) if m <= 2 or n <= 2 : return marked = [[0 for _ in range(n)] for _ in range(m)] #感觉有点类似于走迷宫的感觉 能否走到终点 #可以有一个保存可以escape的数组 保存位置 def escape(x, y): directions = [[-1, 0], [0, 1], [1, 0], [0,-1]] for item in directions: new_x = x + item[0] new_y = y + item[1] if x == 3 and y ==3: print("33", new_x, new_y, marked[new_x][new_y]) #需要判断合法以及 各种情况 if 0 <= new_x <= m-1 and 0 <= new_y <= n-1 and not marked[new_x][new_y]: #到达边界且可以出去 if new_x == 0 or new_x == m-1 or new_y == 0 or new_y == n-1: if board[new_x][new_y] == 'O': return True else: if x == 3 and y ==3: print(x, y, new_x, new_y) if board[new_x][new_y] == 'O': if x == 3 and y ==3: print("----------", x, y, new_x, new_y) marked[x][y] = 1 if not escape(new_x, new_y): #某个方向出不去 也不能returnFalse print("don't escape new" ,new_x,new_y) board[new_x][new_y] = 'X' else: #下一个可以出去 这个也可以出去 return True marked[x][y] = 0 else: continue else: continue return False
for i in range(1, m-1):
for j in range(1, n-1):
if board[i][j] == 'O':
#去寻找出路
print(i,j)
if not escape(i, j):
board[i][j] = 'X'
print("don't escape", i, j)
return
#出现了循环 不停的重复 用mark标记之后 出现了新的问题 有33 由32过去 暂时搁置
class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ if not board: return m = len(board) n = len(board[0]) if m <= 2 or n <= 2 : return marked = [[0 for _ in range(n)] for _ in range(m)] #感觉有点类似于走迷宫的感觉 能否走到终点 #可以有一个保存可以escape的数组 保存位置 def escape(x, y): directions = [[-1, 0], [0, 1], [1, 0], [0,-1]] for item in directions: new_x = x + item[0] new_y = y + item[1] if x == 3 and y ==3: print("33", new_x, new_y, marked[new_x][new_y]) #需要判断合法以及 各种情况 if 0 <= new_x <= m-1 and 0 <= new_y <= n-1 and not marked[new_x][new_y]: #到达边界且可以出去 if new_x == 0 or new_x == m-1 or new_y == 0 or new_y == n-1: if board[new_x][new_y] == 'O': return True else: if x == 3 and y ==3: print(x, y, new_x, new_y) if board[new_x][new_y] == 'O': if x == 3 and y ==3: print("----------", x, y, new_x, new_y) marked[x][y] = 1 if not escape(new_x, new_y): #某个方向出不去 也不能returnFalse print("don't escape new" ,new_x,new_y) board[new_x][new_y] = 'X' else: #下一个可以出去 这个也可以出去 return True marked[x][y] = 0 else: continue else: continue return False
for i in range(1, m-1):
for j in range(1, n-1):
if board[i][j] == 'O':
#去寻找出路
#print(i,j)
if not escape(i, j):
board[i][j] = 'X'
print("don't escape", i, j)
return
#出现了循环 不停的重复 用mark标记之后 出现了新的问题 有33 由32过去 暂时搁置
#出现了问题 不用mark标记 会出现不停的重复回溯调用 往返调用 如果用mark标记 会出现除了来的方向可以出去， 另外3个方向出不去 从而导致错误标记