Check if a master string contains all the strings given in a list. Also, strings should not overlap.
example:
1) "indiaismycountry" is a master string which contains all strings {"is", "country, india"}.
2) "animal" is a master string which doesn't contains {"an", "animal"}.
This question not form any running contest. I is asked in a interview.
Any solution or useful link will be helpful.
Thanks in advance!
Auto comment: topic has been updated by K_B_C_S (previous revision, new revision, compare).
First of all sort the list strings in decreasing order according to length and the check for every string one by one and check two conditions ,
If string is not found in master string then return "false"
If string is found in master string then (replace it with *) them from master string.
If all the string satisfied condition 2nd return "True"
can you explain your approach with "monkeyoumonkeyuo" as master string and {"monkey", "you"} as list of string?
first search monkey , monkey is in master string then replace monkey (replace which monkey which does not contain any other string) from master string the master string becomes (monkeyou******uo).
Then search you in master string it is found in master string) so answer is TRUE.
UPD : don't delete , replace it with ******
How will you decide that a string doesn't contain any other string?
This can be check but time limit exceeded.
This is wrong. Simple example:
baaba
,{"a", "baab"}
. After finding and removinga
, the string will becomebaba
, and the last one string is left, however, it could be found if we searched forbaab
first.I already says that sort the strings in decreasing order according to length.
Yes, missed that. However, it is still wrong:
abcbc
,{bc, ab}
. Removingbc
yieldsa**bc
, andab
is left, however searching in the reverse order would find bothab
andbc
.Yes, You are right but what about this one
I've already responed in that thread that my initial approach was wrong. The list needs to be topologically sorted before searching.
What's wrong with my This approach
Nothing's wrong, but how do you choose the ranges such that they do not interleave?
connect all range of (i)th string of (i + 1)th string ranges according to condition that (two ranges connect if they do not overlap.
then range of (i + 1)th string to (i + 2)th string range and so on ...
and at last find a path if we can reach from 1st string to the last string..
if there is a path then answer is "YES" otherwise "NO"
Replacing with asterisks instead of deleting does not fix the problem.
(a, b)
if there is a suffix ofa
which is a prefix ofb
. We do a regular toposort of this graph. Then, we reverse the order.false
.true
.Steps 1-2 are essentially Rabin-Karp algorithm. Could be replaced with any string search algorithm of your choice.
Master string contains other characters as well.
on the step 4, if you came to the end of the string, and the set is nonempty, you start from the next character. Why is it working?
We assume that the first character doesn't belong to any string from the list, Therefore, we skip it.
You are skipping first character this i understood.
I am asking, are you reseting the set or not for next iteration?
How will it work for master string "monkeyouxzmonkeyuo" and {"monkey", "you"}
In this example skipping starting character only can't solve right?
You have to skip 'x', 'z' also.
You can skip several characters in a row. In you case it won't skip any, because
monkey
andyou
are found one after the other. But, for example, inmonkeyxxxyou
, we will skip three characters (xxx
).No, 'y' is common.
This is the thing, how is your approach skipping xxx in monkeyxxxyou?
Haha, yes, it seems that approach is wrong, it fails on the same example I've provided for starboy_jb. When one string has a prefix that is a suffix of another the order of which string to search for first matters. I'll update the comment.
Store the all the occurring range of a string.
And then find the non — interleaving range from all the range.
If it found then "YES" otherwise "NO"
for ex: master string = "monkeyoumonkeyuo"
for the string "monkey" = ( {0 , 5} , {8 , 13} )
for the string "you" = ( {5 , 7} )
then non-interleaving range (must choose one range from all strings) = ( {8 , 13} , {5 , 7} )
so the answer is "YES"