識別字串 [Python3]
識別字串 是 LintCode(詳見 LintCode介紹)所提供的一道 簡單 級別的面試題，現在我對Python3的實作做以簡單分析，如有不妥之處，歡迎指正，
題目描述
給定一組n個僅包含小寫字母的字串，為每個字串找出能夠唯一識別該字串的最小前綴
即可以識別A串的最小前綴Ap，不會是其他n-1個字串的前綴，
1 <= n <= 500；
字串長度不超過100；
如果一個字串S是另一個字串T的前綴，則S的最小可識別前綴為S，
樣例
看完題目描述有沒有感覺比較繞？看個樣例就可以了：
輸入:[“aaa”,“bbc”,“bcd”]
輸出:[“a”,“bb”,“bc”]
解釋:“a"僅是"aaa” 的前綴；
"bb"僅是"bbc"的前綴；
"bc"僅是"bcd"的前綴；
即我們需要的是找到屬于每個字串所特有的最短前綴，要求該前綴不會在其他字串中重復出現，如樣例中所給出的"bbb" 以及"bcd"：由于"b"在兩者中均出現，所以不能直接取"b"作為符合要求的最短前綴，繼續往后讀，前者讀到"bb"而后者讀到"bc"出現不同前綴（即獨有前綴）便可以作為符合要求的前綴，輸出即可，
代碼實作[Python3]
class Solution:
def ShortPerfix(self, stringArray):
if not stringArray:
return []
prefix = {}
for string in stringArray:
for idx in range(len(string)):
prefix[string[:idx + 1]] = prefix.get(string[:idx + 1], 0) + 1
res = []
for string in stringArray:
for idx in range(len(string)):
if prefix[string[:idx + 1]] == 1:
res.append(string[:idx + 1])
break
if idx == len(string) - 1:
res.append(string)
return res
第一行定義類Solution（解決方案）這是LintCode所要求的部分，只是為了順利進行代碼測驗，不必要過多闡述，
主要功能在于函式ShortPerfix，其帶有一個引數stringArray（self是作為有class前提的必要引數，之后代碼并沒有呼叫，所以這里不再講解），引數stringArray 是一個輸入的字串陣列，也就是我們將進行前綴識別的字串陣列，
函式首先執行了一個簡單判斷句 if not stringArray 考慮了空字串的情況，若輸入空，則回傳空，隨后定義一個perfix來存盤可能得到的前綴長度，string[:idx + 1] 表示截取字串string從起始位置到索引為 idx + 1 位置的字串，
接下來，利用for回圈遍歷輸入陣列中所有字串，然后根據每個字串的長度（len(string)）獲取其可能存在的最短前綴長度，
下一步進行前綴判斷，使用了2個if來判斷不同情況，第一個：若所得前綴在idx + 1處長度為1，則將此前綴加入res（即最終輸出的陣列）中，第二個：若此時索引值為字串長度減一（即前綴為整個字串），則直接把字串加入res中，
最終輸出所得 res 結果，
更好的方案
在剛才的分析中，細心的朋友們就會發現，在整個程式中執行了兩次字串陣列遍歷，且把獲取前綴和判斷前綴分成了兩部分，這樣的寫法確實通俗易懂，但使得程式運行的時間達不到最快(LintCode上該代碼測驗平均耗時 302 ms ，這已經很快了)，
以下是一個極好的解決方案（僅 201 ms）：
class Solution:
def ShortPerfix(self, stringArray):
from collections import defaultdict
Trie = lambda: defaultdict(Trie)
root = Trie()
for string in stringArray:
p = root
for c in string:
p = p[c]
if '#' not in p:
p['#'] = 0
p['#'] += 1
p['$'] = True
ans = []
for string in stringArray:
p = root
cur = ""
for c in string:
p = p[c]
cur += c
if p['#'] == 1:
ans.append(cur)
break
else:
ans.append(string)
return ans
這個寫法就很高級，高級到我看不懂，它好像是直接在collections中引入一種預設類實體化然后進行一頓十分高級的操作就完成了判斷，這段代碼真的看得頭暈眼乏，希望有大佬講解一下，
感謝瀏覽（點個贊再走唄）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257114.html
標籤：python