查找其他字符串的前綴字符串

這是一個面試問題。給定一些字符串可以找到這樣的字符串，這些字符串是其他字符的前綴。例如，給出strings = {"a", "aa", "ab", abb"}的結果是{"a", "ab"}。查找其他字符串的前綴字符串

最簡單的解決方案就是對字符串進行排序，並檢查每個對的兩個後續字符串，如果第一個字符串是第二個字符串的前綴。算法的運行時間是排序的運行時間。

我想還有另一種解決方案，它使用trie，並且複雜度爲O(N)，其中N是字符串的數量。你能建議這樣的算法嗎？

2012-07-09 Michael

恐怕排序解決方案不會給你這樣的運行時間。假設你有{「a」，「aa」，「aaa」} - 你可以將它們排序爲O（nlog（n）），但是你仍然需要檢查「a」是否爲「aa」的前綴， a「是」aaa「的前綴，」aa「是」aaa「的前綴 - 給你O（n^2） – Archeg 2012-07-09 14:36:08

@Michael我提供了一種算法，我相信它可以解決你在O（N）中的問題，但是你永遠不會評論它。你有沒有發現我的解決方案是正確的？如果是這樣，請將其標記爲正確答案，如果不是，那麼我想聽聽您的意見 – Martinsos 2013-04-04 11:44:25

我有一個關於特里接下來的想法，複雜度爲O（N）：你開始用空的特里。你一個一個接一個字，然後給Trie添加單詞。後添加一個字（姑且稱之爲字無線）到特里，有兩種情況考慮：

無線是一些你之前添加的話前綴。如果您在添加單詞Wi時沒有將任何節點添加到Trie，則該說法是正確的。在這種情況下，Wi是前綴，也是我們解決方案的一部分。
之前添加的一些單詞是Wi的前綴。如果你通過節點代表某個單詞的結尾，那麼這個陳述就是真實的（讓我們調用這個單詞Wj）。在這種情況下，Wj是Wi的前綴和我們解決方案的一部分。

在更多的細節（僞）：

for word in words 
    add word to trie 
    if size of trie did not change then // first case 
     add word to result 
    if ending nodes found while adding word // second case 
     add words defined by those nodes to result 
return result

添加新詞來特里：

node = trie.root(); 
for letter in word 
    if node.hasChild(letter) == false then // if letter doesnt exist, add it 
     node.addChild(letter) 
    if letter is last_letter_of_word then // if last letter of word, store that info 
     node.setIsLastLetterOf(word) 
    node = node.getChild(letter) // move

當你添加新詞，你也可以檢查，如果你通過任何節點傳遞代表其他單詞的最後一個字母。我描述的算法的複雜性是O（N）。另一個重要的事情是，這樣你可以知道多少次Wi前綴其他詞，這可能是有用的。

示例{AAB，AABA，AA}：綠色節點是檢測作爲殼體1 紅色節點是檢測作爲殼體2 每一列（線索）節點的節點是一個步驟。開始時，trie是空的。黑色箭頭顯示我們在該步驟中訪問（添加）了哪些節點。表示某個單詞的最後一個字母的節點將該單詞寫入父項。

enter image description here

在步驟1中，我們添加單詞AAB。
在步驟2中，我們添加單詞aaba，識別一個案例2（單詞aab）並添加單詞aab。
在第3步中，我們添加單詞aa，識別第1個單詞並添加單詞aa以生成結果。

最後我們得到結果= {aab，aa}這是正確的。

來源

2012-07-09 14:40:45 Martinsos

原始答案對：是字符串a a 子串的b（誤讀）。

使用一個trie，您可以在第一次迭代中簡單地將所有字符串添加到它，並在第二次迭代中，開始讀取每個單詞，讓它成爲w。如果你發現一個單詞，你完成了你的閱讀，但沒有達到字符串終止符（$通常），你到達一些節點v在trie中。
通過從v執行DFS，您可以獲得所有字符串，其中w是它們的前綴。

高級別僞代碼：

t <- new trie 
for each word w: 
    t.add(w) 
for each word w: 
    node <- t.getLastNode(w) 
    if node.val != $ 
    collection<- DFS(node) (excluding w itself) 
    w is a prefix of each word in collection

注：爲了優化它，你可能需要做一些額外的工作：如果a是b前綴，b是c前綴，那麼a是因此 - 當您執行DFS時，如果您到達某個已經搜索到的節點 - 只需將其字符串附加到當前前綴。
不過，由於可能存在二次數的可能性（"a", "aa", "aaa", ....），所有這些都需要二次時間。

原來的答覆：如果發現是a一個子的b：

建議的解決方案在二次運行的複雜性，你需要檢查每一個兩雙，給你O(n* (n-1) * |S|)。

您可以在第一次迭代中從字符串中構建一個suffix tree，並在第二次迭代中檢查每個字符串是否是另一個字符串的非平凡條目（而不是本身）。
該解決方案是O(n*|S|)

來源

2012-07-09 14:33:15 amit

我猜基數樹也可以在這裏使用相同數量的操作。像Archeg所說， – Archeg 2012-07-09 14:52:26

可以用一個Radix Tree來節省Trie的空間。 – Justin 2012-07-09 16:45:59

查找其他字符串的前綴字符串

回答

相關問題