Each step of the Levenshtein distance

Question

In this challenge you will write a program that takes two newline-separated strings, s1 (the first line) and s2 (the second line), as input (STDIN or closest). You can assume that the length of s1 will always be smaller than 30 and bigger than the length of s2. The program should then output each step in the levenshtein distance from s1 to s2.

To clarify what each step in the levenshtein distance means, the program will print n strings, where n is the levenshtein distance between s1 and s2, and the levenshtein distance between two adjacent strings will always be one. The order doesn't matter. The output should be newline-separated and not include s1, only the in-betweens and s2. The program should also run in under one minute on a modern computer.

Examples:

Input:

Programming
Codegolf

Output:

rogramming
Cogramming
Coramming
Coamming
Codmming
Codeming
Codeging
Codegong
Codegolg
Codegolf

Input:

Questions
Answers

Output:

uestions
Aestions
Anstions
Ansions
Answons
Answens
Answers

Input:

Offline
Online

Output:

Ofline
Online

Input:

Saturday
Sunday

Output:

Sturday
Surday
Sunday

Here is a link to a python script that prints out the distance and the steps.

Additional rules:

• No use of the internet
• Standard loopholes apply

This is code-golf so keep you code short; shortest code wins!

Answer 1

Haskell, 201 194 bytes

l=length
g[]n u=map(\_->"")n
g(b:c)[]u=(u++c):g c[]u
g(b:c)n@(o:p)u|b==o=g c p(u++[o])|1<2=((u++o:c):g c p(u++[o]))!((u++c):g c n u)
a!b|l a<l b=a|1<2=b
p[a,n]=g a n""
f=interact$unlines.p.lines

Longer than expected. Maybe I can golf it down a little bit ...

Usage example:

*Main> f                     -- call via f
Questions                    -- User input
Answers                      -- no newline after second line!
uestions                     -- Output starts here
Aestions
Anstions
Ansions
Answons
Answens
Answers

It's a brute force that decides between changing and deleting if the initial characters differ.

Answer 2

APL (Dyalog 18.0), 66 bytes

{⍺<Ö≢⍵:⍺∇⎕←0~⍨0@(⊃(⍸~p)~⍳⊃⌽⍸p←⍵=⍺↑⍨≢⍵)⊢⍵⋄j←⊃⍸⍺≠⍵⋄⍺≢⍵:⍺∇⎕←⍺[j]@j⊢⍵}

Try it online!

Works correctly now.

A recursive function submission, done with a lot of input from Adám and Bubbler.

Input is taken as <s2> f <s1>.

Explanation

⍺<⍥≢⍵: if the strings have different lengths:

0@(...)⊢⍵ put a zero at the following index:

⊃ first element of:

(⍸~p) characters which do not match

~ without

⍳⊃⌽⍸p←⍵=⍺↑⍨≢⍵ all indices before last character match

0~⍨ remove the zero(thereby removing the element)

⍺∇⎕← display the result and recurse

⋄⍺≢⍵: Otherwise, till the strings match:

i←⊃⍸⍺≠⍵ find first non-matching element

⍺[i]@i⊢⍵ and replace the element at that index

⍺∇⎕← display the result, and recurse