【力扣 中等 C】79. 单词搜索

发布于:2025-07-03 ⋅ 阅读:(26) ⋅ 点赞:(0)

目录

题目

解法一:回溯


题目

解法一:回溯

void swap(char* a, char* b) {
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void reverse(char* str) {
    int start = 0, end = strlen(str) - 1;
    while (start < end) {
        swap(&str[start++], &str[end--]);
    }
}
 
bool search(char** board, int m, int n, int i, int j,
    const char* word, int index) {
    if (word[index] == '\0') {
        return true;
    }
 
    if (i < 0 || i == m || j < 0 || j == n || 
        word[index] != board[i][j]) {
        return false;
    }
 
    board[i][j] = '#';
    bool exist = 
        search(board, m, n, i - 1, j, word, index + 1) || 
        search(board, m, n, i + 1, j, word, index + 1) || 
        search(board, m, n, i, j - 1, word, index + 1) || 
        search(board, m, n, i, j + 1, word, index + 1);
    board[i][j] = word[index];
    return exist;
}
 
bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    const int m = boardSize, n = *boardColSize;
 
    int boardLetterCnts[128] = {0};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            boardLetterCnts[board[i][j]]++;
        }
    }
 
    int wordLetterCnts[128] = {0};
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        wordLetterCnts[word[i]]++;
    }
 
    for (int i = 'A'; i <= 'Z'; i++) {
        if (boardLetterCnts[i] < wordLetterCnts[i] || 
            boardLetterCnts[i + 32] < wordLetterCnts[i + 32]) {
            return false;
        }
    }
    
    char newWord[len + 1];
    strcpy(newWord, word);
    if (wordLetterCnts[word[0]] > wordLetterCnts[word[len - 1]]) {
        reverse(newWord);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (search(board, m, n, i, j, newWord, 0)) {
                return true;
            }
        }
    }
    return false;
}


网站公告

今日签到

点亮在社区的每一天
去签到