130. Surrounded Regions
可以分為三個(gè)步驟
- 初始化一個(gè)list或deque
queue = collections.deque([])系吭，遍歷矩陣，將所有位于矩陣邊緣上的O的坐標(biāo)存起來(lái)
for i in range(m):
for j in range(n):
if (i in [0, m-1] or j in [0, n-1]) and board[i][j] == 'O':
queue.append((i, j))
- 遍歷queue中的元素坐標(biāo)颗品，將每個(gè)等于O的元素的上下左右鄰居坐標(biāo)都存入queue中肯尺，如果i,j滿(mǎn)足條件沃缘，且元素等于'O', 就先將其設(shè)為'S'
while queue:
i, j = queue.popleft()
if m > i >=0 and n > j >= 0 and board[i][j] == 'O':
board[i][j] = 'S'
queue.append((i-1,j)); queue.append((i+1, j));
queue.append(i, j-1); queue.append((i, j+1))
將上下左右鄰居都加進(jìn)去做檢查的原因是，有可能O沒(méi)有被X圍住则吟，這時(shí)我們就要保留O在原位置上槐臀。特殊情況有：[OOO, OOO,OOO]
- 再次遍歷數(shù)組，將元素為'O'的氓仲，賦值為'X'水慨，將元素為'S'的，還原成'O'
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'S':
board[i][j] = 'O'
127. Word Ladder
先將endword放入wordlist里去寨昙，然后初始化一個(gè)元素為list類(lèi)型的deque讥巡，先將startword和length = 1放進(jìn)去，當(dāng)queue不為空時(shí)舔哪，就pop出當(dāng)前的第一個(gè)word
wordlist.append(endword) queue = collections.deque([]) queue.append([startword, 1])
while queue:
word, length = queue.popleft()
if word == endword:
return length
for i in range(len(word)):
for j in 'abcdefghijklmnopqrstuvwxyz':
if word[i] != j:
nextword = word[:i] + j + word[i+1:]
if nextword in wordlist:
wordlist.remove(nextword)
queue.append([nextword, length+1])
每次pop出來(lái)一個(gè)單詞后欢顷，通過(guò)BFS來(lái)構(gòu)造與它只差一個(gè)字母的newword，如果newword存在wordlist里捉蚤，就證明這個(gè)就是我們要找的下一個(gè)單詞抬驴，先將它從wordlist里刪除，避免重復(fù)訪(fǎng)問(wèn)缆巧，然后再將它append到queue里布持，以便進(jìn)行下一步查找，并且length要加1. 最后如果得不到endword陕悬，就返回0
