LeetCode #212 Word Search II

Word_Search_II.png

/**
* Further improvements're possible by utilizing a trie...
*/
bool dfs(char **table, int m, int n, int i, int j, bool **flag, char *word, int wi, int wn) {
    if (i >= 0 && i < m  && j >= 0 && j < n && wi < wn && *(*(table + i) + j) == *(word + wi) && !(*(*(flag + i) + j))) {
        (*(*(flag + i) + j)) = true;
        if (wi == wn - 1) return true;
        if (i - 1 >= 0 && *(*(table + i - 1) + j) == *(word + wi + 1) && !(*(*(flag + i - 1) + j))) {
            if (dfs(table, m, n, i - 1, j, flag, word, wi + 1, wn)) return true;
        } 
        if (i + 1 < m && *(*(table + i + 1) + j) == *(word + wi + 1) && !(*(*(flag + i + 1) + j))) {
            if (dfs(table, m, n, i + 1, j, flag, word, wi + 1, wn)) return true;
        }
        if (j - 1 >= 0 && *(*(table + i) + j - 1) == *(word + wi + 1) && !(*(*(flag + i) + j - 1))) { 
            if (dfs(table, m, n, i, j - 1, flag, word, wi + 1, wn)) return true;
        }
        if (j + 1 < n && *(*(table + i) + j + 1) == *(word + wi + 1) && !(*(*(flag + i) + j + 1))) {
            if (dfs(table, m, n, i, j + 1, flag, word, wi + 1, wn)) { return true; }
        }
        *(*(flag + i) + j) = false;
        return false;
    } else {
        return false;
    }
}

bool exist(char** board, int boardSize, int* boardColSize, char * word){
    int m = boardSize, n = *boardColSize, wn = strlen(word);
    bool **flag = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        *(flag + i) = (bool*)malloc(n * sizeof(bool));
        for (int j = 0; j < n; j++) { *(*(flag + i) + j) = false; }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            bool result = dfs(board, m, n, i, j, flag, word, 0, wn);
            if (result) return true;
        }
    }
    return false;
}

char ** findWords(char** board, int boardSize, int* boardColSize, char ** words, int wordsSize, int* returnSize){
    char **foundWords = (char**)malloc(wordsSize * sizeof(*foundWords));
    *returnSize = 0;
    for (int i = 0; i < wordsSize; i++) { 
        if (exist(board, boardSize, boardColSize, words[i])) { 
            foundWords[(*returnSize)++] = words[I];
        }
    }
    return foundWords;
}