Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Word search with branching logic and the addition of a seen cache and early return
var exist = function(board, word) {
var seen = [];
var targetCharIdx = 0;
var result = {
found: false
};
var seenCache = {};
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[0].length; j++) {
if (result.found) return result.found;
if (board[i][j] === word[targetCharIdx]) {
seen.push([i,j]);
addCellToSeenCache([i,j], seenCache);
targetCharIdx++;
existHelper(board, word, seen, result, targetCharIdx, [i,j], seenCache);
removeCellFromSeenCache([i,j], seenCache);
targetCharIdx--;
seen.pop();
}
}
}
return result.found;
};
var existHelper = function(board, word, seen, result, targetCharIdx, currCell, seenCache) {
if (word.length === seen.length) {
result.found = true;
} else {
var adjCells = adjacentCells(currCell, board);
for (var i = 0; i < adjCells.length; i++) {
var adjCell = adjCells[i];
if (!alreadySeen(adjCell, seenCache) && isRightChar(adjCell, word[targetCharIdx], board)) {
seen.push(adjCell);
addCellToSeenCache(adjCell, seenCache);
existHelper(board, word, seen, result, targetCharIdx + 1, adjCell, seenCache);
removeCellFromSeenCache(adjCell, seenCache);
seen.pop(adjCell)
}
}
}
};
function addCellToSeenCache(cell, seenCache) {
var cellString = cell[0].toString() + cell[1].toString();
seenCache[cellString] = true;
}
function removeCellFromSeenCache(cell, seenCache) {
var cellString = cell[0].toString() + cell[1].toString();
seenCache[cellString] = false;
}
function isRightChar(cell, char, board) {
return board[cell[0]][cell[1]] === char
}
function adjacentCells(currCell, board) {
return [[currCell[0] + 1, currCell[1]],
[currCell[0] - 1, currCell[1]],
[currCell[0], currCell[1] + 1],
[currCell[0], currCell[1] - 1]
]
.filter(function(cell) {
return (cell[0] >= 0 && cell[1] >= 0) &&
(cell[0] < board.length && cell[1] < board[0].length)
});
};
function alreadySeen(currCell, seenCache) {
var currCellString = currCell[0].toString() + currCell[1].toString();
return !!seenCache[currCellString]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.