目录
题目
解法一:回溯
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;
}