Design a data structure to store strings efficiently for following operations :
1. IsPrefix (s1, s2) : Is s1 a prefix of s2.
2. IsEqual(s1, s2) : Are s1 and s2 equal.
3. common prefix(s1, s2) : Return the common prefix of the given strings s1 and s2.

Question

Design a data structure to store strings efficiently for following operations : 
1. IsPrefix (s1, s2) : Is s1 a prefix of s2.
2. IsEqual(s1, s2) : Are s1 and s2 equal.
3. common prefix(s1, s2) : Return the common prefix of the given strings s1 and s2.

Kurt · Accepted Answer

Reverse the strings and use a suffix tree. (A suffix tree is a type of radix tree.)

Gaurav Kalra · Answer

Suffix Array ?

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas