給定一個二維矩陣的字符，我們必須檢查給定的字是否存在

給定一個二維矩陣的字符，我們必須檢查給定的字是否存在。如給定一個二維矩陣的字符，我們必須檢查給定的字是否存在

s f t 
d a h 
r y o

我們可以發現「老鼠在它 （自頂向下，直，斜或anypath）..甚至在相反的順序，與至少complexiety。

我的做法是

While traversing the 2d matrix (a[][]) row wise. 
If (a[i][j] == first character of given word) { 
    search for rest of the letters in 4 directions i.e. right, right diagonally down, down and left diagonally down. 
} else if(a[i][j] == last character of the given word) { 
    search for remaining characters in reverse order in 4 directions i.e. left, right diagonally up, up, left diagonally up. 
}

有沒有更好的方法嗎？

來源

2013-06-23 user2416871

什麼最好的方法是在一定程度上取決於對單詞的規則，你沒有說清楚點，這個問題是可以解決的再次撥打您的功能。一個單詞的字母必須在一條直線上，還是會有任何路徑？一條路徑可以跨越自己，和/或重新使用字母嗎？此外，還有兩個不同的O（）函數適用於：一個用於預處理，一個用於搜索。經過預處理後，您可能會首先尋找罕見的字母或罕見的元組 –

這裏的一個重要問題是：要搜索的單詞的最大長度是多少？這可以改變整個故事。 – Aravind

事實上你在這裏16個序列：

sft 
dah 
ryo 
sdr 
fay 
tho 
sao 
rat 
tfs 
had 
oyr 
rds 
yaf 
oht 
oas 
tar

（3水平+ 3垂直+ 2個對角線）* 2（反轉）= 16設n是一大小的矩陣。在你的例子中n = 3。序列數=（n + n + 2）* 2 = 4n + 4。創建一個散列集（C++中的unordered_set，Java中的HashSet）和字典中的單詞（可在Internet上找到）。您可以在O（1）中檢查一個序列。

來源

2013-06-23 15:25:47

任何路徑怎麼樣 –

「任何路徑」根本不準確。什麼是路徑的長度？它可以重疊嗎？有了'任何'的路徑，我只能說你會有'任何'的複雜性。 –

我想我會分兩個階段執行此操作：

1）迭代這個數組，尋找單詞的第一個字母的實例。

2）當你找到第一個字母的實例時，調用一個檢查所有相鄰單元格的函數（例如最多9個），看看它們中的任何一個是否是這個單詞的第二個字母。對於找到的任何第二個字母匹配，這個函數會自動遞歸地調用它，並在與之相鄰的單元格中查找第三個字母的匹配（依此類推）。如果遞歸一直到達單詞的最後一個字母並找到匹配的單詞，那麼該單詞就存在於數組中。（請注意，如果您不允許使用兩次字母，則需要將單元格標記爲'已經使用'，以防止算法重新使用它們。可能最簡單的方法是傳遞 - 通過遞歸函數中的已使用單元座標的矢量，並且遞歸函數忽略列表中的任何單元的內容）

來源

2013-06-23 15:37:54

讓我爲此描述一個非常酷的數據結構問題。

繼續前進，查找嘗試。

需要花費O（k）時間將一個k長度的單詞插入到Trie中，並且O（k）要查找k長度單詞的存在。

Video tutorial

如果你有問題理解數據結構，或者實現它，我會很樂意幫助你。

來源

2013-06-23 15:43:39 Aravind

這不是假定沒有重複嗎？ – beaker

OP要求檢查存在性，不計數，但後者可以很容易地修復。如果你實現了一個trie，那只是對該代碼的一點修改。 – Aravind

對不起，我不是很清楚。我的意思是重複字母，而不是重複字符串例如，不會在下列矩陣中檢測單詞「bat」：'[b n t; a x a; f p j]'？ – beaker

使用一個簡單的循環尋找第一個字母或你的詞，當你發現它使用下面的遞歸函數。

該函數將作爲輸入5個參數：你正在尋找str的話，你目前在str您在陣列k，i和j的位置尋找陣列中搜索這個詞的字母的位置爲信和方向d。

的停止條件是：

- 如果k > strlen(str); return 1;

- 如果arr[i][j] != str[k]; return 0;

如果沒有上表述是正確的，你增加你的信反k++;更新i和j acording您的d價值，並通過return func(str, k);

來源

2013-06-23 15:51:25

給定一個二維矩陣的字符，我們必須檢查給定的字是否存在

回答

相關問題