string algorithm homework/interview like question

Lets say we have to strings, A and B. The task is to insert any needed letters in the string B in order to end up with the string 开发者_如何学运维A.

For example:

A - This is just a simple test 
B - is t a sim te

So if we look at the string A like this:

--is -- ---t a sim--- te--

or:

---- is ---t a sim--- te--

it is clear that we can build string A from the string B, and the output should be in the above written format (both answers are correct).

Can you think of an algorithm that will solve this in the reasonable time? It is quite easy to come up with brute force solution, but I need something a bit more sophisticated than that.

You could take Levenshtein distance algorithm as a base and extend it to also remember the characters that were added/deleted/substituted. That would run in linear time.

You can just find first occurrence of characters of B in A, just start finding occurrence after last index found in A, for example in your case:

A - This is just a simple test 
B - is t a sim te

i: 3rd place in A,
s: 4th place in A,
' ': 5th place in A,
t: 12th place in A, (because last index was 4)
' ': ...
a: ....

That's O(|A|+|B|) and because |A| > |B| it's O(|A|).

After finding indices it's easy to convert B to A, just by adding characters of A between 2 indices to B.

Edit: Also if there is no match this algorithm, works fine (there will be some characters in B which are not in A, from last index).

I would think you could determine if its possible with a nice reg expression. as there may or may not be 1 or more characters between any of the ones suggested in B.

I actually think brute force will be the quickest but you have to mutate string A to do it fastests in one pass... just iterate over A change each letter to "-" that doesn't match the letter you are looking for unless it is a space type of deal... that will be constant time and require no extra storage... basically your time will be N. Of course you have to deal with the tokens from "B" so once you find "i" you need to make sure the next letter is "s" so that you find "is" but is still should be quick just don't go back to the I position if the next letter isn't s... that should point you in the correct direction without giving you the solution to your homework...

I think you could do it in linear time and space, like this (pseudocode, completely untested):

String f( String a, String b ) {
  String result;

  // Iterate over 'a' and 'b' in parallel. If both have the same
  // character, add it to the result. Otherwise, if 'a' has a space add a space to the result, otherwise add a dash.
  int idxB = 0;
  for (int idxA = 0; idxA < a.length(); ++idxA ) {
    if (a[idxA] == b[idxB]) {
      result.append(a[idxA]);
      ++idxB;
    } else if (a[idxA] == ' ') {
      result.append(' ');
    } else {
      result.append('-');
    }
  }

  // Tack on dashes to the result until it's as long as 'a'.
  while (result.length() < a.length()) {
    result.append('-');
  }

  return result;
}