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 单词搜索问题总结

前缀搜索

720. 词典中最长的单词

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)

79. 单词搜索

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)

127. 单词接龙

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 单词翻转

单词原地翻转

344. 反转字符串

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))