CareerCup

Trie is the best example for this scenario but careful and smart implementation of trie is required here !!

1.) Given a song name , split the words from song name.
2.) Insert word in Trie if it doesn't exist, Trie as a data structure should have at each node , a list of songs.
3.)So when you insert Every and Everything
Each node till y in Every should point to list of two songs and after y should point to one song only.

Trie is a good example for this scenario but this requires smart implementation of trie

#include<iostream>
#include<string>
using namespace std;

void dictionary(string niti,string in)
{
size_t found= niti.find(in);

if(found!=string::npos)
cout<<niti<<endl;
}


int main()
{
string in="night in";

string str[]={"Every night in my dreams","Listen to my heart","show me the meaning","night in london","night changes"};

int n= sizeof(str)/sizeof(str[0]);

for(int i=0;i<n;i++)
dictionary(str[i],in);
return 0;
}

It is a mixture of trie search. Store songs in vector and then in trie search, on each node, where word has been formed, save the indexes of songs in list. So in case if song "Every night in my dreams", it can go to E, N, I , M and D word and insert the index in list for nodes - Every, night, in , my, dreams. Now if user has type m, find all word by using trie search and caluclate the list of songs available on nodes by removing duplicates. return that.

use a suffix trie to solve it

jhj

knnnnnnnnnnnnnnnnnnnnnnnnnnnnnn