Uber Coding Interview Question - Word Search - Leetcode 79

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[sebaitor]

This can be solved in O(nm) since once you find the first letter it's trivial to check neighbours in order to complete the word

[PSBhat-xdgp]

Greg, can you please link your code for every video? It’s easier that way!

[Aryeh-o]

overall a fun graph problem, I really like lattices.

[Aryeh-o]

The big deal is finding the first A
you can use cache for that
the rest of the word is 9*len(word) steps worst case.

Maybe you can use caching or mark-off bad edges from the graph while you search, in case you end up backtracking and want to narrow the search space.

but I doubt it's effective!