c語言怎么實現單詞搜索

C語言怎么實現單詞搜索

在C語言中，實現單詞搜索功能可以通過多種方式來完成。本文將介紹一種基于二維字符數組的單詞搜索算法。該算法可以在一個二維字符數組中查找指定的單詞，并返回單詞的起始位置。

問題描述

假設我們有一個二維字符數組 grid，其中包含了一些字母。我們的任務是在這個數組中查找一個給定的單詞 word，并返回單詞的起始位置。如果單詞存在，返回 true；否則返回 false。

算法思路

1. 遍歷二維數組：首先，我們需要遍歷整個二維數組，尋找與單詞第一個字符匹配的位置。

2. 深度優先搜索（DFS）：對于每一個匹配的位置，我們使用深度優先搜索（DFS）來檢查是否可以從該位置開始，沿著上下左右四個方向找到完整的單詞。

3. 邊界條件：在DFS過程中，我們需要確保不會超出數組的邊界，并且已經訪問過的位置不會被重復訪問。

4. 回溯：如果在某個方向上無法找到匹配的字符，我們需要回溯到上一個位置，嘗試其他方向。

代碼實現

#include <stdbool.h>
#include <string.h>

#define ROWS 3
#define COLS 4

bool dfs(char grid[ROWS][COLS], int i, int j, char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) {
        return true;
    }

    if (i < 0 || i >= ROWS || j < 0 || j >= COLS || visited[i][j] || grid[i][j] != word[index]) {
        return false;
    }

    visited[i][j] = true;

    if (dfs(grid, i + 1, j, word, index + 1, visited) ||
        dfs(grid, i - 1, j, word, index + 1, visited) ||
        dfs(grid, i, j + 1, word, index + 1, visited) ||
        dfs(grid, i, j - 1, word, index + 1, visited)) {
        return true;
    }

    visited[i][j] = false;
    return false;
}

bool exist(char grid[ROWS][COLS], char *word) {
    bool visited[ROWS][COLS] = {false};

    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(grid, i, j, word, 0, visited)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    char grid[ROWS][COLS] = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };

    char word[] = "ABCCED";

    if (exist(grid, word)) {
        printf("Word found!\n");
    } else {
        printf("Word not found.\n");
    }

    return 0;
}

代碼解釋

1. dfs 函數：這是一個遞歸函數，用于在二維數組中進行深度優先搜索。它檢查當前位置是否匹配單詞的當前字符，并遞歸地檢查四個方向。

2. exist 函數：這個函數遍歷整個二維數組，調用 dfs 函數來查找單詞。

3. main 函數：在 main 函數中，我們定義了一個二維字符數組 grid 和一個單詞 word，然后調用 exist 函數來查找單詞。

運行結果

如果單詞存在于二維數組中，程序將輸出 "Word found!"；否則輸出 "Word not found."。

總結

通過使用深度優先搜索（DFS）算法，我們可以在C語言中實現一個簡單的單詞搜索功能。該算法的時間復雜度為 O(N * M * 4^L)，其中 N 和 M 是二維數組的行數和列數，L 是單詞的長度。雖然這個算法在最壞情況下可能比較慢，但對于大多數實際應用來說，它已經足夠高效。