/* if either string is empty, difference is inserting all chars
         * from the other
         */
        if (!ls) return lt;
        if (!lt) return ls;

        /* if either string is empty, difference is inserting all chars
         * from the other
         */
        if (!(ls*lt)) return ls+lt;

10 REM ZX Spectrum Levenshtein
20 INPUT "first word:", n$
30 INPUT "second word:", m$
40 LET r=LEN n$+LEN m$:DIM n(r):DIM m(r):DIM e(r)
50 LET n(2)=LEN n$:LET m(2)=LEN m$:LET n(1)=n(2)+1:LET m(1)=m(1)+1:LET r=1
60 GOSUB 1000
70 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";e(2);"."
80 STOP
1000 LET r=r+1
1010 IF n(r)=0 THEN LET e(r)=m(r):LET r=r-1:RETURN
1020 IF m(r)=0 THEN LET e(r)=n(r):LET r=r-1:RETURN
1030 IF n$(n(r) TO n(r))=m$(m(r) TO m(r)) THEN LET n(r)=n(r)-1:LET m(r)=m(r)-1:GOTO 1010
1040 LET n(r+1)=n(r)-1:LET m(r+1)=m(r)-1:GOSUB 1000:LET e(r)=e(r+1)
1050 IF n(r-1)>n(r) THEN LET n(r+1)=n(r)-1:LET m(r+1)=m(r):GOSUB 1000:if e(r+1)<e(r) THEN LET e(r)=e(r+1)
1060 IF m(r-1)>m(r) THEN LET n(r+1)=n(r):LET m(r+1)=m(r)-1:GOSUB 1000:if e(r+1)<e(r) THEN LET e(r)=e(r+1)
1070 LET e(r)=e(r)+1:LET r=r-1:RETURN