CODEWITHSUNDEEP
stringalgorithm
doekman
doekman

Reputation: 19288

How to mark the differences between two strings

I want a function that would visually mark the differences between two strings.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

I've searched for this a lot, but I always end up with file compare functions. I want to visualise the difference between strings. One example I found is https://text-compare.com (this is exactly what I need), but it appears to use server-side code.

Language doesn't matter much, JavaScript, Python, but any pointers how to approach this problem would be nice.

I'm not necessarily looking for an implementation; I'd rather have some links to some website, since this is not an elementary problem. Not too difficult either, but you want to get it right.

Upvotes: 2

Views: 836

Answers (1)

kaya3
kaya3

Reputation: 51092

This problem can be solved by finding the longest common subsequence (LCS) of the two strings, then putting the square brackets around only those parts which are not part of the LCS.

For example, the LCS of Stack Overflow and Stack ooverflowing is Stack verflow, so the first string would be rendered as Stack [O]verflow and the second as Stack [oo]verflow[ing], because those are the parts not present in the LCS.

There is a standard dynamic programming algorithm for computing the LCS which is described on Wikipedia, and various optimisations to this algorithm which speed it up in practical cases. The parts of each string which are not present in the LCS can be found by a simple loop maintaining the current index in the string and another index for the current position in the LCS.

Upvotes: 6

Related Questions