單詞搜尋：回顧方法的經典示例和 C 語言的解決方案

要學習工控知識，就來工控小鑫。

農曆十一月29th，2024 1：10

2024 年 1 月 9 日，每天花一分鐘練習 C。

2024 年 1 月 8 日，每天花一分鐘練習 C。

每天練習一次

daily exercises

單詞搜尋。

給定乙個 m x n 二維字元網格板和乙個字串字。 如果網格中存在單詞，則返回 true; 否則，返回 false。

單詞必須由相鄰單元格中的字母按字母順序組成，其中“相鄰”單元格是水平或垂直相鄰的單元格。 同一單元格中的字母不允許重複使用。

為了實現回溯方法，我們需要定義乙個輔助函式，該函式以遞迴方式在網格中搜尋單詞的每個字母。 此函式需要接收以下引數：

- board：2D角色網格

- word：您要查詢的單詞

- index：您當前要匹配的單詞的字母索引

- x：要匹配的網格的行坐標

- y：要匹配的網格的列坐標

- visited：乙個二維布林陣列，用於跟蹤哪些單元格已被訪問以避免重用

此函式的返回值是乙個布林值，該值指示是否可以從當前位置在網格中找到單詞的其餘部分。 具體邏輯如下：

如果索引等於單詞的長度，則所有字母都已匹配，並返回 true

如果 x 或 y 越界，或者 board[x][y] 不等於 word[index]，或者 visited[x][y] 為 true，則當前位置不滿足條件並返回 false

否則，將 visited[x][y] 設定為 true 以指示已訪問當前位置。

然後，嘗試從當前位置的四個方向繼續搜尋：上、下、左、右，只要乙個方向成功，就返回 true

最後，將 visited[x][y] 設定為 false，表示可以重新訪問當前位置，並返回 false

有了這個輔助函式，我們可以寫出 main 函式，用於遍歷網格中的每個位置，作為搜尋的起點，呼叫輔助函式，如果返回 true，則表示該詞被找到，否則繼續遍歷，直到遍歷所有位置，如果沒有找到， 返回 false。

專案介紹

下面是我用 C 語言編寫的完整程式，您可以在 VC6 中找到0 執行並除錯它：

程式測試

為了驗證我們的程式是否正確，我們可以使用一些測試用例來驗證這一點。

給定乙個字串，驗證它是否為回文字串，僅考慮字母和數字字元，並忽略字母的大小寫。

注意：在這個問題中，我們將空字串定義為有效的回文字串。

示例 1：輸入："a man，aplan，a canal: panama

輸出：true

解釋：“amanaplanacanalpanama”是回文字串示例2：

輸入："race a car"

輸出：false