Вот формулировка проблемы для тех, кто не знаком с этой проблемой:
Учитывая двумерную доску и слово, найдите, существует ли слово в сетке. Слово может быть составлено из букв последовательно смежных ячеек, где «смежные» ячейки - это те, которые соседствуют по горизонтали или вертикали. Одну и ту же буквенную ячейку нельзя использовать более одного раза.
Я решил решить эту проблему в Java. В обоих решениях есть функция exist(char[][] board, String word), которая требуется для основного запроса, и я использую вспомогательную функцию DFS() для сути алгоритма (стандартный возврат).
Функция exist() для обоих решений:
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0 || board[0] == null) return false;
if (word.length() > board.length * board[0].length) return false;
char[] w = word.toCharArray();
char a = w[0];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == a && DFS(board,w,i,j,0)) return true;
}
}
return false;
}
Теперь вот функция DFS() для первого подхода. (Обратите внимание, что программа предполагает, что слово никогда не будет содержать символ @, но его можно сделать более сильным, если использовать какой-либо случайный символ Unicode или даже логический массив для полной гарантии):
Решение 1
public boolean DFS(char[][] board, char[] word, int i, int j, int idx) {
if (idx == word.length) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
board[i][j] != word[idx]) return false;
board[i][j] = '@';
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] d : dirs) {
if (DFS(board,word,i+d[0],j+d[1],idx+1)) return true;
}
board[i][j] = word[idx];
return false;
}
И вот второе решение:
Решение 2
public boolean DFS(char[][] board, char[] word, int i, int j, int idx) {
if (idx == word.length) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
board[i][j] != word[idx]) return false;
board[i][j] = '@';
boolean found = false;
found = DFS(board,word,i-1,j,idx+1) || DFS(board,word,i+1,j,idx+1) ||
DFS(board,word,i,j-1,idx+1) || DFS(board,word,i,j+1,idx+1);
board[i][j] = word[idx];
return found;
}
Теперь, насколько я понимаю, с Java короткое замыкание, обе версии DFS() должны перестать исследовать дополнительные пути, если любая подзадача вернет true. Фактически, единственное различие между двумя версиями, которое я могу оценить, заключается в том, что первая не беспокоит сброса платы (в исходную форму без символов @, обозначающих посещенные позиции), если решение найдено, тогда как вторая делает.
Итак, насколько я понимаю, второе решение должно быть на медленнее , чем первое. Но ясно, что я ошибаюсь: решение 1 выполняется за 8 миллисекунд, а решение 2 выполняется за 3 миллисекунды.
Кто-нибудь знает, что мне здесь не хватает?
Спасибо