Skip to content

Instantly share code, notes, and snippets.

@codyromano
Created August 21, 2018 04:17
Show Gist options
  • Save codyromano/21cb71318d791cc80856485b5f5fab92 to your computer and use it in GitHub Desktop.
Save codyromano/21cb71318d791cc80856485b5f5fab92 to your computer and use it in GitHub Desktop.
const findWordsInMatrix = (matrix, dictionary) => {
// Convert dictionary to map for O(1) lookup
// We could also use a trie here (more efficient, but verbose implementation)
const dictionary = dictionary.reduce((set, word) => {
set.add(word);
return set;
}, new Set());
const wordsFound = new Set();
const visited = new Map();
// Start search in upper-lefthand corner
const search = [{
x: 0,
y: 0,
word: matrix[0][0]
}];
while (search.length) {
const { x, y, word } = search.pop();
if (isOutOfBounds(matrix, x, y)) {
continue;
}
// Don't terminate when a word is found because there
// may be compound words
if (dictionary.has(word)) {
wordsFound.add(word);
}
const nearby = getAdjacentSpots(matrix, x, y);
const letterInThisSpot = matrix[x][y];
nearby
.filter(spot => !visited[spot])
.forEach(spot => {
visited[spot] = true;
search.push({
x: spot.x,
y: spot.y,
word: word + letterInThisSpot
})
});
}
return wordsFound;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment