waterloojeongbum
BAN USERMy solution is to think about this directed graph as a trie tree. Let's say we are trying to check if "abc" is valid in START -> a -> b -> c -> END. Starting from the START node, we want to know if there is a neighbor node with "a". If there is, we traverse to the node and see if there exists "b" and so on. Therefore, the most optimal data structure would be to have the graph in adjacency matrix which will result in O(k) time complexity where k is length of string.
Follow-up: Graph has cycle
Since we are traversing through the string that we want to check, it doesn't matter whether there is a cycle in the graph or not. We will traverse k times through the graph at maximum. If there is no END node after, then return false.
Follow-up: Graph has repeated characters
We can use backtracking to solve for this.
Wouldn't this fail for test case: "abcccc" and "cabcccc"?
- waterloojeongbum February 16, 2019