Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
The "dumb" version the backtracking algorithm for the word search problem on LeetCode
var exist = function(board, word) {
var seen = [];
var targetCharIdx = 0;
var result = {
found: false
};
existHelper(board, word, seen, result);
return result.found;
};
var existHelper = function(board, word, seen, result) {
if (word.length === seen.length) {
if (wordMatches(word, seen, board)) {
if (cellsAreUnique(seen)) {
if (cellsAreAdjacent(seen)) {
result.found = true;
}
}
}
} else {
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[0].length; j++) {
seen.push([i, j])
existHelper(board, word, seen, result)
seen.pop();
}
}
}
};
var cellsAreAdjacent = function(seen) {
var i = 0;
var j = 1;
var cellOne;
var cellTwo;
while (j < seen.length) {
cellOne = seen[i];
cellTwo = seen[j];
var diffOne = Math.abs(cellOne[0] - cellTwo[0]);
var diffTwo = Math.abs(cellOne[1] - cellTwo[1]);
if (!xor(diffOne === 1, diffTwo === 1)) {
return false;
}
j += 1;
i += 1;
}
return true;
};
var xor = function(option1, option2) {
return ((option1 || option2) && !(option1 && option2));
};
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.