用於在不同方向搜索網格的算法

今天，一位同事向我提出了一個問題。給定一個字符網格和一個單詞列表，人們必須在網格中水平，垂直和對角地找到該單詞的每個出現位置。用於在不同方向搜索網格的算法

我們想出瞭解決方案，並做了一些小技巧，但我很想看看其他人如何打勾。

來源

2010-07-14 user391671

前進和後退匹配數？ – 2010-07-14 15:27:14

將每個單詞插入列表中的trie或hash table或任何字典。

現在，對於網格中的每個位置，水平，垂直和對角地查看是否在字典中找到匹配項。這應該給你O(N^3)最壞情況的複雜性，其中N是網格的大小。否則它是O(N^2*averageWordLength)我想。

來源

2010-07-14 14:29:45 IVlad

不是'O（N * maxWordLength）'嗎？每個字母只需要檢查長度爲1，2，3，...，maxWordLength的單詞的開始。 – 2010-07-14 16:45:42

與trie相比，哈希表將是一個糟糕的選擇。有了這個線索，一旦你沒有得到任何長度爲k的字符串的匹配，你就可以停止。使用散列表，在嘗試使用所有長度爲n的字符串（n是從字符到邊的距離）之前，您無法停下來。例如，假設您有行（INTABCDE）。 INTEGER一詞在你的字典中。使用trie，你首先嚐試我，它不在字典中，但是是一個有效的路徑。您繼續到A，並且您不再處於有效的路徑中。你不能用散列表來做到這一點，所以你將被迫散列所有可能的字符串。 – 2010-07-14 16:47:04

@BlueRaja - 這就是我說的太實際:)。我的意思是「N」是「N×N」網格的大小（因此它具有N^2個總元素）。如果你認爲'N'是網格中元素的總數，那麼它就是'N'而不是'N^2'。 @Niki - 真的。 – IVlad 2010-07-14 17:34:04

用於在不同方向搜索網格的算法

回答

相關問題