分組字謎

鑑於字的陣列，組字謎 IP：{焦油，大鼠，香蕉，ATR} OP：{[焦油，大鼠，ATR]，[香蕉]}分組字謎

一個解決這個問題使用哈希表。考慮每個單詞，對其進行排序並添加爲散列表的關鍵字（如果不存在）。密鑰的值將是具有相同密鑰的所有字母的列表。我想知道時間複雜性，爲了對數組中的字符進行排序，假設O（n log n）要存儲在散列表中，它將是O（n），總數爲O（n * nlogn）。

有更好的算法嗎？時間複雜度較低？

但是'n'是單詞的長度，而不是數組中的單詞數量，所以它不應該太糟糕。無論如何，你可以定義你自己的哈希函數，這將獨立於重排。例如，將字母值加起來：tar - > 20 + 1 + 18 = 39。但這可能不是一個很好的散列。 – Teepeemm

我看不到這個問題和dup之間的關係。請參閱[這裏]（http://stackoverflow.com/a/18144931/2417578）瞭解與訂單無關的散列。我寫的測試應用程序拋棄了散列和單詞，我通過散列將它們排序在一起，這似乎是你前進的方式。 – sh1

出於時間複雜性的考慮，您始終可以使用計數排序來對單個詞進行排序，這樣每個詞的成本就是線性時間。您也可以首先計算字母的出現次數，然後散列出現次數而不是排序詞，這與計數排序減去重建步驟基本相同。

但是由於這個詞通常會很短，所以這可能不會給您帶來任何實際的好處。

2013-07-29 21:42:18

+1。在大O符號方面，計算字母頻率然後散列它的解決方案肯定優於O（N * M * lg（M）），其中M是最長字符串的長度。因爲根據你的解決方案，它有O（26 * N * M）= O（N * M）。但我同意你說它不會購買任何實際優勢（即使N和M很小，它可能會比OP現在做的更差）:) – Fallen

嗯，這是一個面試問題，我編寫了答案我在我的問題中描述。但是我清楚了面試。所以想知道是否有更好的東西存在。 – user2626431

面試的因素太多，例如你寫的程序有多好？你有沒有做出好的分析？你是一個很好的文化比賽嗎？但算法明智的是，你給出的答案應該足夠了。 –

回答