K_B_C_S's blog

Help in a string question.
By K_B_C_S, history, 6 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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 ,

  1. If string is not found in master string then return "false"

  2. 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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This can be check but time limit exceeded.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, You are right but what about this one

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              What's wrong with my This approach

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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   Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it
  1. 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.
  2. Calculate hashes of strings in the list and store them. Also calculate hashes of prefixes of the master string.
  3. 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.
  4. 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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No, 'y' is common.

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

              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
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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"

→ Reply