Step by Step solution about How to resolve the algorithm Levenshtein distance step by step in the Go programming language

Levenshtein Distance

The provided source code calculates the Levenshtein distance between two strings using two different implementations.

First Implementation (ld function)

• Creates a 2D matrix d where d[i][j] represents the Levenshtein distance between the prefixes of length i in string s and prefixes of length j in string t.
• Initializes the first row and column to be the length of the corresponding string, representing the case when one string is empty and the other is not.
• Iterates over the strings and matrix, comparing characters and updating the distance.
• If characters match, distance remains the same as the diagonal element (d[i-1][j-1]).
• If characters don't match, it calculates the minimum of the following options:
  • Inserting a character (d[i-1][j] + 1)
  • Deleting a character (d[i][j-1] + 1)
  • Substituting a character (d[i-1][j-1] + 1)
• Returns the Levenshtein distance stored in d[len(s)][len(t)].

Second Implementation (levenshtein function)

• This implementation is recursive and operates on the suffix of the strings.
• If either string is empty, the distance is the length of the other string.
• If the first characters match, it recursively calls itself on the suffixes of the strings.
• If characters don't match, it considers three options:
  • Inserting a character (levenshtein(s[1:], t[1:]) + 1)
  • Deleting a character (levenshtein(s, t[1:]) + 1)
  • Substituting a character (levenshtein(s[1:], t) + 1)
• Returns the minimum of the three options.

Main Function

• The main function calls the ld or levenshtein function to calculate the Levenshtein distance between two sample strings.
• It prints the calculated distance to the console.

package main

import "fmt"

func main() {
    fmt.Println(ld("kitten", "sitting"))
}

func ld(s, t string) int {
    d := make([][]int, len(s)+1)
    for i := range d {
        d[i] = make([]int, len(t)+1)
    }
    for i := range d {
        d[i][0] = i
    }
    for j := range d[0] {
        d[0][j] = j
    }
    for j := 1; j <= len(t); j++ {
        for i := 1; i <= len(s); i++ {
            if s[i-1] == t[j-1] {
                d[i][j] = d[i-1][j-1]
            } else {
                min := d[i-1][j]
                if d[i][j-1] < min {
                    min = d[i][j-1]
                }
                if d[i-1][j-1] < min {
                    min = d[i-1][j-1]
                }
                d[i][j] = min + 1
            }
        }

    }
    return d[len(s)][len(t)]
}


package main

import "fmt"

func levenshtein(s, t string) int {
    if s == "" { return len(t) }
    if t == "" { return len(s) }
    if s[0] == t[0] {
        return levenshtein(s[1:], t[1:])
    }
    a := levenshtein(s[1:], t[1:])
    b := levenshtein(s,     t[1:])
    c := levenshtein(s[1:], t)
    if a > b { a = b }
    if a > c { a = c }
    return a + 1
}

func main() {
    s1 := "rosettacode"
    s2 := "raisethysword"
    fmt.Printf("distance between %s and %s: %d\n", s1, s2,
        levenshtein(s1, s2))
}