Jul 20, 2020 · 5 min read
Есть прямоугольная доска с буквами, надо проверить можно ли составить из них указанное слово. Есть возможность перемещаться по доске только вдоль осей координат, т.е. вертикально или горизонтально.
Пример:
- Для слова “ABCCED”, вернуть
true. - Для слова “SEE”, вернуть
true. - Для слова “ABCB”, вернуть
false.
Обратите внимание, что ABCB составить нельзя, потому что одна и та же буква не может использоваться более одного раза.
Решение #
Любое решение стоит начинать с разбора примеров руками, поискать нужные слова маркером на доске.
Глянув на рисунок со стрелочками, по аналогии с задачей про домино, на ум приходит граф. Узлы это буквы, а связи — переходы между ними в разрешённых направлениях.
Задача сводится к поиску определённого пути в графе, стандартной задаче на поиск в глубину (DFS). Важно правильно обработать требование не использовать одну и ту же букву дважды. При рекурсивном обходе графа надо сделить за уже использованными узлами в рамках текущего пути.
В общем случае, для этого можно использовать set: добавлять туда узлы, а когда зашли в тупик — удалять (ну и читать из него не забывать при обходе). «Тупик» это когда понимаем, что пришли в букву которой в слове нет, дальше нет смысла проверять, надо возвращаться и пробовать поискать нужную букву среди соседей.
В нашем случае, можно сэкономить память и использовать уже данное в условии поле. Довольно популярный трюк. Когда заходим в рекурсию надо стирать текущую букву с поля (например, заменить пробелом), а когда выходим — возвращать на место.
Итак, алгоритм следующий:
- перебираем все буквы слева направо
- как только нашлась первая буква слова — запускаем поиск в глубину
- если путь в графе нашёлся — возвращает
true - если путь в графе не нашёлся — продолжаем перебор
- если путь в графе нашёлся — возвращает
- если обошли всё поле и ещё не вышли с
true, значит такого слова нет вовсе
Оценим сложность. В худшем случае рекурсия обойдёт всё клетки поля, сложность O(N) по времени. По памяти так же O(N), потому что рекурсии нужна память под каждый вызов функции на стеке.
Выполнив этот алгоритм по шагам на данных примерах руками, убедившись, что это работает (и получив невербальную реакцию интервьюера, мол, отлично) — можно писать код.
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
const h = board.length;
const w = board[0].length;
// обходим всё поле
for (let y = 0; y < h; y++) {
for (let x = 0; x < w; x++) {
// пытаемся поиска данное слово (путь в графе)
// начиная с текущей буквы на поле
if (dfs(word, 0, y, x)) {
return true;
}
}
}
return false;
};Основная обвязка есть. Теперь самое интересное — реализовать функцию dfs. Кстати, это стандартное название из мира олимпиадного программирования, при поиске в глубину.
Возможно, на собеседовании имеет смысл назвать более осмысленно, например isWordThere.
// Я предполагаю, что функцию разместим внутри exist,
// так что будут доступны переменные
// board, w, h через замыкание,
// но можно передать и через параметры
function isWordThere(word, index, y, x) {
// базовый случай для выхода из рекурсии:
// обошли всё слово.
if (index === word.length - 1) {
return word[index] === board[y][x];
}
// если текущая буква в слове
// не совпадает с той, что на поле
// это «тупик» — дальше не ищем
if (word[index] !== board[y][x]) {
return false;
}
// перед тем как искать следующую букву
// затираем текущую, помечаем как
// «использованную в данном пути»
let cachedValue = board[y][x];
board[y][x] = " ";
// рассматриваем все возможные переходы
for (let [y1, x1] of [[y + 1, x], [y, x + 1], [y - 1, x], [y, x - 1]]) {
// не выходим за границы поля
if (y1 >= 0 && y1 < h && x1 >= 0 && x1 < w) {
// если слово нашлось — отлично,
// вернём true, который всплывёт по стеку вызовов,
// иначе был тупик, надо поискать ещё,
// пусть цикл по всем направлениям работает дальше
if (isWordThere(word, index + 1, y1, x1)) {
return true;
}
}
}
// не забываем вернуть затертый символ на место,
// чтобы можно было использовать его в рамках других путей,
// которые ещё не проверили
board[y][x] = cachedValue;
// здесь понимаем, что обошли все направления
// и везде тупик, вернём false и
// пусть всплывает по стеку
return false;
}На этом всё. Решение целиком:
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
const h = board.length;
const w = board[0].length;
// обходим всё поле
for (let y = 0; y < h; y++) {
for (let x = 0; x < w; x++) {
// пытаемся поиска данное слово (путь в графе)
// начиная с текущей буквы на поле
if (isWordThere(word, 0, y, x)) {
return true;
}
}
}
return false;
function isWordThere(word, index, y, x) {
// базовый случай для выхода из рекурсии:
// обошли всё слово.
if (index === word.length - 1) {
return word[index] === board[y][x];
}
// если текущая буква в слове
// не совпадает с той, что на поле
// это «тупик» — дальше не ищем
if (word[index] !== board[y][x]) {
return false;
}
// перед тем как искать следующую букву
// затираем текущую, помечаем как
// «использованную в данном пути»
let cachedValue = board[y][x];
board[y][x] = " ";
// рассматриваем все возможные переходы
for (let [y1, x1] of [[y + 1, x], [y, x + 1], [y - 1, x], [y, x - 1]]) {
// не выходим за границы поля
if (y1 >= 0 && y1 < h && x1 >= 0 && x1 < w) {
// если слово нашлось — отлично,
// вернём true, который всплывёт по стеку вызовов,
// иначе был тупик, надо поискать ещё,
// пусть цикл по всем направлениям работает дальше
if (isWordThere(word, index + 1, y1, x1)) {
return true;
}
}
}
// не забываем вернуть затертый символ на место,
// чтобы можно было использовать его в рамках других путей,
// которые ещё не проверили
board[y][x] = cachedValue;
// здесь понимаем, что обошли все направления
// и везде тупик, вернём false и
// пусть всплывает по стеку
return false;
}
};PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗
Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.