# Levenshtein Distance for Data Filtering with Typo Tolerance in Swift

**What is Levenshtein Distance?**

Levenshtein distance is a versatile algorithm used to quantify the similarity or dissimilarity between texts in various fields. It is commonly employed in spelling correction systems to rectify misspelled words. Additionally, it finds applications in genetics and bioinformatics to determine similarities between DNA sequences.

**Using Levenshtein Distance in Swift**

Below is a simple example demonstrating how to compute the Levenshtein distance using Swift:

func levenshteinDistance(_ str1: String, _ str2: String) -> Int { let len1 = str1.count let len2 = str2.count var matrix = Array(repeating: Array(repeating: 0, count: len2 + 1), count: len1 + 1) for i in 0...len1 { matrix[i][0] = i } for j in 0...len2 { matrix[0][j] = j } for i in 1...len1 { for j in 1...len2 { let index1 = str1.index(str1.startIndex, offsetBy: i-1) let index2 = str2.index(str2.startIndex, offsetBy: j-1) if str1[index1] == str2[index2] { matrix[i][j] = matrix[i-1][j-1] } else { matrix[i][j] = min(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + 1) } } } return matrix[len1][len2] } let distance = levenshteinDistance("kitten", "sitting") print(distance) // Output: 3

In the above example, the `levenshteinDistance`

function takes two strings as parameters and computes the Levenshtein distance. The function initializes variables `len1`

and `len2`

to represent the lengths of the two strings. Then, it creates a matrix and assigns initial values to it.

**Filtering Data with Typo Tolerance**

let cities = ["New York", "San Francisco", "Los Angeles", "Chicago", "Seattle", "Boston"] func filterCities(with query: String, tolerance: Int) -> [String] { var filteredCities: [String] = [] for city in cities { let distance = levenshteinDistance(city.lowercased(), query.lowercased()) if distance <= tolerance { filteredCities.append(city) } } return filteredCities } let searchQuery = "New Yrk" let toleranceThreshold = 2 let filteredResult = filterCities(with: searchQuery, tolerance: toleranceThreshold) print(filteredResult) // Output: ["New York"]

In the above example, we have an array called `cities`

containing various city names. The `filterCities`

function takes two parameters: `query`

represents the search query, and `tolerance`

defines the maximum allowed Levenshtein distance for a match.

Within the function, we iterate over each city in the `cities`

array and calculate the Levenshtein distance between the lowercase version of the city name and the lowercase version of the search query. If the distance is less than or equal to the tolerance threshold, the city is considered a match and added to the `filteredCities`

array.

Finally, we call the `filterCities`

function with the search query “New Yrk” and a tolerance threshold of 2. The function returns an array with the filtered result, which in this case is `["New York"]`

due to the tolerance for typos.