966. 元音拼寫檢查器
class Solution:def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:origin = set(wordlist) # 存儲原始單詞用于完全匹配lower_to_origin = {} # 存儲小寫形式到原始單詞的映射vowel_to_origin = {} # 存儲元音模糊形式到原始單詞的映射trans = str.maketrans("aeiou", "?????") # 創建元音替換表（小寫）# 構建映射字典（優先保留先出現的單詞）for s in wordlist:lower_s = s.lower()# 小寫形式映射：僅當鍵不存在時添加if lower_s not in lower_to_origin:lower_to_origin[lower_s] = s# 元音模糊形式映射：先轉為小寫再替換元音vowel_s = lower_s.translate(trans)if vowel_s not in vowel_to_origin:vowel_to_origin[vowel_s] = s# 處理每個查詢res = []for q in queries:# 1. 完全匹配（區分大小寫）if q in origin:res.append(q)continuelower_q = q.lower()# 2. 不區分大小寫匹配if lower_q in lower_to_origin:res.append(lower_to_origin[lower_q])continue# 3. 元音模糊匹配vowel_q = lower_q.translate(trans)if vowel_q in vowel_to_origin:res.append(vowel_to_origin[vowel_q])else:res.append("") # 無匹配返回空字符串return res1. 類和方法的定義
spellchecker?方法，該方法的主要功能是實現一個拼寫檢查器。它接收兩個參數：一個單詞列表?wordlist?和一個查詢列表?queries，并返回一個與?queries?長度相同的列表，列表中的每個元素是對相應查詢的最佳匹配結果
2. 初始化數據結構
origin = set(wordlist)
lower_to_origin = {}
vowel_to_origin = {}
trans = str.maketrans("aeiou", "?????") # 替換元音為 '?'
origin：將?wordlist?轉換為集合，用于快速檢查某個單詞是否在原始單詞列表中，因為集合的查找操作時間復雜度為?O(1)。lower_to_origin：一個字典，用于存儲小寫形式的單詞到原始單詞的映射，方便進行不區分大小寫的匹配。vowel_to_origin：一個字典，用于存儲將元音字母替換為?'?'?后的小寫單詞到原始單詞的映射，用于不區分大小寫且元音模糊匹配。trans：使用?str.maketrans()?方法創建一個字符映射轉換表，將元音字母?'a'、'e'、'i'、'o'、'u'?替換為?'?'。
3. 遍歷單詞列表，構建映射關系
for s in reversed(wordlist):lower = s.lower()lower_to_origin[lower] = s # 例如 kite -> KiTevowel_to_origin[lower.translate(trans)] = s # 例如 k?t? -> KiTe
- 使用?
reversed(wordlist)?反向遍歷單詞列表，這樣在有多個匹配時，優先選擇單詞列表中靠后的單詞。 lower = s.lower()：將當前單詞轉換為小寫形式。lower_to_origin[lower] = s：將小寫形式的單詞作為鍵，原始單詞作為值存入?lower_to_origin?字典，用于不區分大小寫的匹配。lower.translate(trans)：使用之前創建的字符映射轉換表?trans，將小寫單詞中的元音字母替換為?'?'。然后將替換后的單詞作為鍵，原始單詞作為值存入?vowel_to_origin?字典，用于不區分大小寫且元音模糊匹配。
4. 遍歷查詢列表，進行匹配操作
for i, q in enumerate(queries):if q in origin: # 完全匹配continuelower = q.lower()if lower in lower_to_origin: # 不區分大小寫的匹配queries[i] = lower_to_origin[lower]else: # 不區分大小寫+元音模糊匹配queries[i] = vowel_to_origin.get(lower.translate(trans), "")
- 使用?
enumerate(queries)?同時獲取查詢單詞的索引?i?和單詞?q。 if q in origin:：檢查查詢單詞是否在原始單詞列表中，如果是，則不做處理，繼續處理下一個查詢。lower = q.lower()：將查詢單詞轉換為小寫形式。if lower in lower_to_origin:：檢查小寫形式的查詢單詞是否在?lower_to_origin?字典中，如果是，則將查詢結果替換為對應的原始單詞。else:：如果不滿足上述條件，則進行不區分大小寫且元音模糊匹配。使用?lower.translate(trans)?將小寫查詢單詞中的元音字母替換為?'?'，然后使用?vowel_to_origin.get()?方法查找對應的原始單詞。如果找到則替換查詢結果，否則將查詢結果替換為空字符串。
5. 返回結果
return queries
最后返回經過匹配處理后的查詢列表。
示例代碼運行
from typing import Listclass Solution:def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:origin = set(wordlist)lower_to_origin = {}vowel_to_origin = {}trans = str.maketrans("aeiou", "?????") # 替換元音為 '?'for s in reversed(wordlist):lower = s.lower()lower_to_origin[lower] = s # 例如 kite -> KiTevowel_to_origin[lower.translate(trans)] = s # 例如 k?t? -> KiTefor i, q in enumerate(queries):if q in origin: # 完全匹配continuelower = q.lower()if lower in lower_to_origin: # 不區分大小寫的匹配queries[i] = lower_to_origin[lower]else: # 不區分大小寫+元音模糊匹配queries[i] = vowel_to_origin.get(lower.translate(trans), "")return queries# 示例調用
solution = Solution()
wordlist = ["KiTe", "kite", "hare", "Hare"]
queries = ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"]
result = solution.spellchecker(wordlist, queries)
print(result)
這段代碼通過構建不同的映射關系，實現了三種類型的拼寫匹配：完全匹配、不區分大小寫的匹配和不區分大小寫且元音模糊匹配。
