Help in a string question.

6 years ago, # |

Auto comment: topic has been updated by K_B_C_S (previous revision, new revision, compare).

→ Reply

6 years ago, # |

← Rev. 3 →

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"

→ Reply

6 years ago, # ^ |

can you explain your approach with "monkeyoumonkeyuo" as master string and {"monkey", "you"} as list of string?

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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 ******

→ Reply

6 years ago, # ^ |

How will you decide that a string doesn't contain any other string?

→ Reply

6 years ago, # ^ |

This can be check but time limit exceeded.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

This is wrong. Simple example: baaba, {"a", "baab"}. After finding and removing a, the string will become baba, and the last one string is left, however, it could be found if we searched for baab first.

→ Reply

6 years ago, # ^ |

I already says that sort the strings in decreasing order according to length.

→ Reply

6 years ago, # ^ |

Yes, missed that. However, it is still wrong: abcbc, {bc, ab}. Removing bc yields a**bc, and ab is left, however searching in the reverse order would find both ab and bc.

→ Reply

6 years ago, # ^ |

Yes, You are right but what about this one

→ Reply

6 years ago, # ^ |

I've already responed in that thread that my initial approach was wrong. The list needs to be topologically sorted before searching.

→ Reply

6 years ago, # ^ |

What's wrong with my This approach

→ Reply

6 years ago, # ^ |

Nothing's wrong, but how do you choose the ranges such that they do not interleave?

→ Reply

6 years ago, # ^ |

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"

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Replacing with asterisks instead of deleting does not fix the problem.

→ Reply

6 years ago, # |

← Rev. 6 →

Perform topological sorting of the list. We assume a directed edge between items (a, b) if there is a suffix of a which is a prefix of b. We do a regular toposort of this graph. Then, we reverse the order.
Calculate hashes of strings in the list and store them. Also calculate hashes of prefixes of the master string.
Search for each string using sliding window technique, from the start of the master string. Track characters of the master string which belong to the found items. When encountering such character, start over from the next one. If an item is not found, return false.
All items are found, return true.

Steps 1-2 are essentially Rabin-Karp algorithm. Could be replaced with any string search algorithm of your choice.

→ Reply

6 years ago, # ^ |

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?

→ Reply

6 years ago, # ^ |

We assume that the first character doesn't belong to any string from the list, Therefore, we skip it.

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

You can skip several characters in a row. In you case it won't skip any, because monkey and you are found one after the other. But, for example, in monkeyxxxyou, we will skip three characters (xxx).

→ Reply

6 years ago, # ^ |

No, 'y' is common.

This is the thing, how is your approach skipping xxx in monkeyxxxyou?

→ Reply

6 years ago, # ^ |

← Rev. 4 →

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.

→ Reply