+1 vote
in Data Structures & Algorithms I by (88.2k points)
What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

(a) O(S1)

(b) O(S2)

(c) O(S1+S2)

(d) O(1)

This interesting question is from Propositional and Directed Acyclic Word Graph topic in section Graph of Data Structures & Algorithms I

This question was posed to me during an online interview.

1 Answer

+1 vote
by (737k points)
selected by
Best answer
Correct option is (a) O(S1)

Easiest explanation - For each check of a word of length  S1, we need to follow at most S1 edges.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.