Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Slightly improved approach to word search using adjacent cell branching rather than checking for adjacent property at the end of path
var exist = function(board, word) {
var seen = [];
var targetCharIdx = 0;
var result = {
found: false
};
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[0].length; j++) {
if (board[i][j] === word[targetCharIdx]) {
seen.push([i,j]);
targetCharIdx++;
existHelper(board, word, seen, result, targetCharIdx, [i,j])
targetCharIdx--;
seen.pop();
}
}
}
return result.found;
};
var existHelper = function(board, word, seen, result, targetCharIdx, currCell) {
if (word.length === seen.length) {
if (wordMatches(word, seen, board)) {
if (cellsAreUnique(seen)) {
result.found = true;
}
}
} else {
var adjCells = adjacentCells(currCell, board);
for (var i = 0; i < adjCells.length; i++) {
var adjCell = adjCells[i];
seen.push(adjCell);
existHelper(board, word, seen, result, targetCharIdx, adjCell)
seen.pop(adjCell)
}
}
};
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)
});
};
var cellsAreUnique = function(seen) {
var usedCoordinates = {};
var lookup = '';
for (var i = 0; i < seen.length; i++) {
lookup = seen[i][0].toString() + seen[i][1].toString();
if (usedCoordinates[lookup]) {
return false;
}
usedCoordinates[lookup] = true;
}
return true;
};
var wordMatches = function(word, seen, board) {
var constructedWord = '';
seen.forEach(function(coordinate) {
constructedWord += board[coordinate[0]][coordinate[1]];
});
return constructedWord === word;
};
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.