在超過百萬個字符串的列表中以相反順序排列的字符串對？

最近在一些採訪中詢問，「如何找到所有字符串的反向，如果存在超過百萬字符串的列表中？在超過百萬個字符串的列表中以相反順序排列的字符串對？

例如str [1] =」abc「，我需要檢查」cba「確切地說，沒有字謎。

方法1.存儲所有的HashSet的琴絃，開始從第一個字符串遍歷並檢查反轉形態存在的Hashset中，如果是的話，其他配對移動到下一個元素。

如果內存是約束，你能提出任何方法嗎？

來源

2011-09-29 amit mathapati

在重 - 不清楚你是否想在同一個列表中找到所有與他人相反的字符串，或者給定一個字符串，在列表中找到與其相反的字符串。後者當然是一個簡單的搜索問題，在你反轉給定的字符串之後。 –

雖然我在這方面同意丹尼爾的觀點，但考慮到MEMORY是一個約束條件，那根本就不重要。 –

@DanielRHicks我編輯了我的問題....他的意思是，對於列表中的所有字符串查找是否存在相反的... –

你可以使用Bloom Filter它會告訴你一個字符串是否已經存在於像結構這樣的散列表中，但是每個存儲桶只有0或1，因此使用的空間很小。

正好是1個000 000位== 125 KB

來源

2011-09-29 23:43:44 Serdalis

1.）這將需要更多的內存。 2）你不需要很長的字符串來獲得很多長度相同的字符串。 –

你是對的，我會改變我的答案。 – Serdalis

答覆已更改。 – Serdalis

如果允許的話，你可以就地排序琴絃所以當你查找的字符串的反向，你可以做一個二進制搜索。

來源

2011-09-29 23:50:02

首先我會使用獨立於方向的散列來散列字符串。這可能是一個簡單的字符總和，儘管從兩端都會有更好的方案。爲了「促成交易」，可以將字符串長度附加到散列值，否則將其併入散列中。

然後，當你把這些字符串分解成相同的散列組時，請做「長手」比較。

請注意，使用這種方案或者您只是簡單地使用方向依賴哈希向前或向後的方法，所要做的就是不要立即將字符串插入哈希集，而是檢查它（與反向首先，如果需要散列（如果需要散列），並且如果你得到一個匹配（並且隨後的長比較爲真），則刪除已經散列的字符串並將它們配對。第二個字符串永遠不會進入集合，並且，如果所有字符串最多隻有匹配的哈希集合中只有500,000個條目，並且如果字符串是隨機的，則可能接近250,000（我沒有坐下下來以計算概率）。

所以你只需要通過一組字符串來完成整個事情。

來源

2011-09-29 23:52:39

做一個方向獨立的哈希值不會給你任何實際的好處，但肯定會增加碰撞率。 –

獨立於方向的散列將「abc」和「cba」散列到同一個存儲桶中。這大大減少了您必須嘗試的組合數量。 –

我不明白。它爲什麼會減少任何東西？你在說什麼組合？ –

隨着「 內存作爲約束」，那麼我甚至不會去一個HashSet（其中，據我所知也將刪除原始列表複製的字符串），因爲你將要使用的附加結構一個需要一些內存的HashSet。

~~排序，也不會改善內存使用情況。~~

~~我會使用原始列表（它已經存在，因此不會使用額外的內存）+一個3字節的整數變量來迭代列表。 3個字節可以在2^24 = 16777216字符串~~

的列表，包括「內存作爲約束」迭代我會去2環。我認爲C-like僞代碼會更容易理解我的純英文。

注：

問題中已提供的例子，它實際上不是一個列表而是一個數組，所以我會在結構上進行操作，就好像它是一個數組
問題不清楚如何配對這個「abc」，「def」，「cba」，「abc」。我會將第一個「abc」與「cba」配對，並且將「cba」與「第二個abc」配對（問題的意圖還不清楚）
我假設我們無法修改原始列表

這裏是至少內存消耗代碼我能想到的：

// "list" holds the original list (array) 
for (int i = 0; i < length(list) - 1; i++) { 
    for (int j = i + 1; j < length(list); j++) { 
     if (list[i] == reverse(list[j])) { 
      print(list[i] + " reversed is " list[j]) 
     } 
    } 
}

關於存儲器使用，這種解決方案將需要2個整數變量（每一個通常爲4個字節）+原始列表，我假設我們不能擺脫

關於CPU usag e（實際上，根據問題無關），字符串將被顛倒的次數將爲：（N *（N + 1））/ 2其中N是列表的長度

來源

2011-09-29 23:52:58

1,000,000,000,000次迭代，或多或少。（不包括實際的比較循環。） –

嗯，沒有。在列表中迭代1次。這個解決方案的順序是N.但正如我所說的那樣，要求的人明確表示，沒有必要儘快做到這一點，但只需要最少的內存。該列表已經存在，我只是增加了3個字節。您的解決方案需要多少個附加字節？ –

所以請解釋一下如何通過列表中的一個通道來識別列表中的所有反轉重複項。 –

您可以選擇HashTable並使用桶來減少哈希衝突。我們現在需要爲一個特定的查詢字符串做的只是反轉它，將它散列並在HashTable中查找，而不是從開始到結束遍歷。

來源

2011-09-30 02:24:28

是的，這與我的方案基本相同，只有兩倍的哈希值。 –

這是強制我認爲：

我將創建一個哈希與

關鍵字符=

值=字符串列表與該字符開始

現在開始一個循環，你需要從第一個字符串開始。
扭轉它
採取的第一個字符和搜索中的散列該鍵
然後在該值，它包含一個字符串列表，找到字符串在該列表中

來源

2011-09-30 05:16:51 Vijay

在超過百萬個字符串的列表中以相反順序排列的字符串對？

回答

相關問題