CODEWITHSUNDEEP
stringalgorithm
Ayush Goyal
Ayush Goyal

Reputation: 29

Given a string A and a set of string S. Need to find an optimum method to find a prefix of A which is not a prefix of any of the strings in s

Example 

A={apple}

S={april,apprehend,apprehension}

Output should be "appl" and not app since app is suffix of both "apple" and "apprehension" but "appl" is not.

I tried to do this by finding the longest common prefix of A with every string in S and then the answer will be the longest of these prefixes. But this method takes a lot of time since A is also a part of a set of strings and I have to do this for all such strings.

Please suggest an optimum approach.

Upvotes: 0

Views: 78

Answers (2)

fharreau
fharreau

Reputation: 2337

As you only ask for an optimum approach, here it is:

You need to create a trie from your vector S and then walk down the tree, character by character from your string A.

It will be much more efficient than your first approach.

If you need help for implementing this approach, you can ask a new question.

Upvotes: 1

Ambika
Ambika

Reputation: 594

You can use Trie data structure here.

Insert all strings in Set S in trie

now traverse string A in trie in dfs manner

        You will get your prefix, when you'll get null during 
        traversal

I am taking a short example for better view.

Let say A = "rama"; and B {"shy","raku","rio"}

Now after first trie become like below

               ROOT
          /     |  
        s       r    
      /      /     \
     h       a      i
    /      /       /
   y      k       o
         /  
        u

Now in second step traverse "ramu" in dfs manner, we'll get null on reaching 'm' of string "ramu"

So "ram" is required answer.

Upvotes: 0

Related Questions