0X00 单词比较问题总结
比较两个单词所用字符是否相同
a = "aaabbbcccddd"
b = "abcdabcdabcd"
def comapre(a, b):
if len(a) != len(b):
return False
r1, r2 = [0] * 256, [0] * 256
for c in a:
r1[ord(c)] += 1
for c in b:
r2[ord(c)] += 1
for i in range(256):
if r1[i] != r2[i]: return False
return True
print(comapre(a, b))
0X01 单词搜索问题总结
前缀搜索
class Solution:
def longestWord(self, words: List[str]) -> str:
trie = {}
for word in words:
p = trie
for idx, c in enumerate(word):
p = p.setdefault(c, {})
p['#'] = word
# dfs 搜索
self.depth = 0
self.ans = ""
def dfs(node, depth):
if '#' in node:
if depth > self.depth:
self.ans = node['#']
self.depth = depth
elif depth == self.depth:
self.ans = min(self.ans, node['#'])
if len(node) == 1: return
for k, v in node.items():
if k != "#" and '#' in v: dfs(v, depth+1)
# print(trie)
dfs(trie, 1)
return self.ans
这个 trie 容易写错....
相关题目有:
网格搜索(dfs)
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(board) == 0: return False
m, n = len(board), len(board[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(x, y, visited, idx):
if idx >= len(word): return True
if x < 0 or y < 0 or x >= m or y >= n: return False
if word[idx] != board[x][y]: return False
for dx, dy in dirs:
x1, y1 = x + dx, y+dy
if (x1, y1) in visited: continue
if dfs(x1, y1, visited|{(x1, y1)}, idx+1):
return True
return False
for x in range(m):
for y in range(n):
if dfs(x, y, {(x, y)}, 0): return True
return False
单个字母差异搜索(bfs)
from collections import deque
import string
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# bfs
# 不可重复计算
visited = set(wordList)
if endWord not in visited: return 0
if beginWord in visited: visited.remove(beginWord)
deq = deque([beginWord])
m = len(beginWord)
# 注意 step 的最后值
step = 1
while len(deq) > 0:
size = len(deq)
# print(deq)
while size > 0:
size -= 1
word = deq.popleft()
# 构造新单词
for i in range(m):
newWords = [word[:i] + c + word[i+1:] for c in string.ascii_lowercase]
# print(newWords)
for w in newWords:
if w not in visited: continue
if w == endWord: return step + 1
visited.remove(w)
deq.append(w)
step += 1
return 0
0X02 单词翻转
单词原地翻转
b = "123456789"
s = list(b)
def reverse(s):
left, right = 0, len(s)-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
reverse(s)
print("".join(s))
句子中的单词翻转
先翻转整个字符串, 然后按照分割符翻转单词
