查找矩陣中的有效字

給定字典詞典，兩個API Is_word（字符串） Is_prefix（字符串）以及一個NxN矩陣，每個位置由一個字符組成。如果從任何位置（i，j）可以在四個方向中的任何一個方向移動，請找出矩陣中可以形成的所有有效單詞。（循環是不允許的，也就是說，如果從（i，j）開始並移動到（i-1，j），然後從此位置移動到，則形成字位置，則不能返回到（i，j））查找矩陣中的有效字

什麼我trie ::我可以看到一個指數解決方案，我們去所有的可能性和跟蹤已訪問的索引。我們能有更好的解決方案嗎？

來源

2012-07-12 user973931

所以你想要解決一個類似於遊戲般的遊戲？ HTTP：//計算器。com/questions/746082/how-to-find-list-of-a-letter-matrix-boggle-solver – argentage 2012-07-13 04:38:08

這是我能做的最好的：

列舉所有可能在允許的方向的半存儲串。（您可以反轉字符串以獲取其他方向。）
對於每個字符串中的每個起始字符位置，建立子字符串直到它們既不是單詞也不是前綴。

編輯：我可能誤解了這個問題。我認爲每個單詞只能由同一方向的動作組成。

來源

2012-07-12 23:42:59 Neil

它仍然是指數型 – CommonMan 2012-07-13 00:06:14

只需使用一半允許的方向並顛倒弦就可以了不會產生所有可能的解如果從起始字母開始採用以下路徑構建字符串：「東 - 南 - 西」。這個字符串不可能僅通過使用兩個允許的方向來構造。 – Alderath 2012-07-17 13:23:50

我會傾向於通過創建兩個並行數據結構來解決這個問題。一個是單詞列表（刪除重複項）。另一種是前綴矩陣，其中每個元素都是一個列表。希望可以使用這樣的數據結構。列表矩陣實際上可以是三元組列表，其中原始矩陣中包含單詞和座標。

無論如何，通過原始矩陣並在每個元素上調用isword（）。如果有單詞，則將單詞插入單詞列表中。

然後通過原始矩陣，並比較每個元素上的調用isprefix（）。如果有前綴，則插入前綴矩陣。

然後，通過前綴矩陣並測試前綴與附加字母的四種組合。如果一個單詞，然後放在單詞列表中。如果有前綴，則添加到前綴矩陣中的最後一個字母的位置。由於一個詞可以是一個前綴，所以請記住做這兩個。

此外，在前綴列表中，您不僅需要保留一個列表中的字母列表，而且還要保留已使用的字母的位置。這用於防止循環。

然後繼續此過程，直到沒有詞語和前綴。

很難衡量這個結構的複雜性，因爲它似乎取決於字典的內容。

來源

2012-07-13 02:03:30

我認爲你不能在這裏擊敗指數。證明？

想一想，如果你有一個矩陣，你要排列字母，這樣每個組合就是一個有效的字典單詞，例如當你從[i，j]開始時， [i，j]與[i-1，j]或[i + 1，j]或[i，j + 1]或[i，j-1]組合都是2個字母單詞，並且遞歸地繼續長度n的組合（根據你的規則）是一個詞。在這種情況下，你不可能比暴力強。

來源

2012-07-13 05:31:28 user1168577

查找矩陣中的有效字

回答

相關問題