Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Move word matching from end-of-path to branching logic
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) {
result.found = true;
}
var adjCells = adjacentCells(currCell, board);
for (var i = 0; i < adjCells.length; i++) {
var adjCell = adjCells[i];
if (!alreadySeen(adjCell, seen) && isRightChar(adjCell, word[targetCharIdx], board)) {
seen.push(adjCell);
existHelper(board, word, seen, result, targetCharIdx + 1, adjCell)
seen.pop(adjCell)
}
}
};
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, seen) {
var lookup = '';
var currCell = currCell[0].toString() + currCell[1].toString();
for (var i = 0; i < seen.length; i++) {
lookup = seen[i][0].toString() + seen[i][1].toString();
if (lookup === currCell) {
return true;
}
}
return false;
}
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.