Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

Return to Answer

Source Link
ais523
  • 11
  • 19
  • 35

Jelly, 10 bytes

ŒP€f/ṪLạẈS

Try it online!

A port to Jelly of my Brachylog answer, saving a few bytes through more convenient plumbing and some convenient builtins (and beating the builtin-based practical language answers by being shorter than the word "Levenshtein"). This is a function submission (although it also works as a full program), taking a list of the two strings.

The algorithm is the same: find the longest common subsequence of the two strings, then add together the differences in lengths between the common subsequence and each of the two original strings.

An odd side effect of this algorithm is that it seems to give an internally consistent definition of the edit difference between three or more strings, as well. I'm not sure if that would be useful for anything, but it's nice to know it exists.

Explanation

ŒP€f/ṪLạẈS
 € On each of the original strings
ŒP produce all possible subsequences of the string;
 f take the list of common elements
 / between the first and second sets of subsequences;
 L take the length of
 Ṫ the last of these common elements;
 ạ take the absolute differences between that and
 Ẉ the length of each {of the original strings}
 S and sum them.

Shoutouts to here for having an implied "each" in it, thus ensuring that Jelly implicitly finds the correct thing to take the length of (if you write L, "length", rather than , "length of each", you get the number of strings you started with which is not helpful).

Jelly sorts the subsequences in order from shortest to longest, and f returns its output in the same order as in its left argument, so the is guaranteed to find the longest subsequence. We can save any need to subtract from 0 (like the Brachylog submission does), because we have access to an absolute-difference builtin.

Post Made Community Wiki by ais523

AltStyle によって変換されたページ (->オリジナル) /