CODEWITHSUNDEEP
lcs
SomethingSomething
SomethingSomething

Reputation: 12226

LCS (Longest Common Subsequence) - get best K solutions

The LCS problem gets two strings and returns their longest common subsequence.

For example:

LCS on the strings: elephant and eat is 3, as the whole string eat is a subsequence in elephant - indices 0,6,7 or 2,6,7

Another example:

LCS on the strings: elephant and olives is 2, as their longest common subsequence is le

The question is, whether there is an algorithm that does not only returns the most optimal solution, but that can return the K best solutions?

Upvotes: 0

Views: 357

Answers (1)

user8962667
user8962667

Reputation:

There is an algorithm to return all the optimal solutions (I think this is what you asked).

As in Wikipedia:

Using the dynamic programming algorithm for two strings, the table is constructed, then backtracked from the end to the beginning recursively, with the added computation that if either of (i, j-1) or (i-1, j) could be the point preceding the current one, then both paths are explored. This leads to exponential computation in the worst case.

There can be an exponential number of these optimal sequences in the worst case!

Upvotes: 0

Related Questions