Write a program that calculates the levenshtein distance and between two words. the…
- User
Write a program that calculates the levenshtein distance and between two words. the program must return true if the word is within 1 in distance else it should be false
Assistant
Here's a C# program that calculates the Levenshtein distance between two words and returns
trueif the distance is 1 or less, otherwisefalse.Levenshtein Distance Explanation
The Levenshtein distance measures the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another.
Program Code
using System; class Program { static void Main() { Console.Write("Enter the first word: "); string word1 = Console.ReadLine(); Console.Write("Enter the second word: "); string word2 = Console.ReadLine(); int distance = ComputeLevenshteinDistance(word1, word2); bool isWithinOneEdit = distance <= 1; Console.WriteLine($"Levenshtein Distance: {distance}"); Console.WriteLine($"Is within 1 edit? {isWithinOneEdit}"); } static int ComputeLevenshteinDistance(string s, string t) { if (string.IsNullOrEmpty(s)) return string.IsNullOrEmpty(t) ? 0 : t.Length; if (string.IsNullOrEmpty(t)) return s.Length; int[,] distance = new int[s.Length + 1, t.Length + 1]; for (int i = 0; i <= s.Length; i++) distance[i, 0] = i; for (int j = 0; j <= t.Length; j++) distance[0, j] = j; for (int i = 1; i <= s.Length; i++) { for (int j = 1; j <= t.Length; j++) { int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; distance[i, j] = Math.Min( Math.Min( distance[i - 1, j] + 1, // Deletion distance[i, j - 1] + 1), // Insertion distance[i - 1, j - 1] + cost); // Substitution } } return distance[s.Length, t.Length]; } }How It Works
- Input: The program takes two words from the user.
- Levenshtein Calculation:
- It initializes a matrix to store distances.
- Fills the first row and column with incremental values (representing insertions/deletions).
- Computes the minimum distance by comparing characters and updating the matrix.
- Result:
- If the distance is ≤ 1, it returns
true. - Otherwise, it returns
false.
- If the distance is ≤ 1, it returns
Example Outputs
- Input:
"kitten","sitting"→ Distance: 3 →false - Input:
"cat","cats"→ Distance: 1 →true - Input:
"hello","hallo"→ Distance: 1 →true
This program efficiently checks if two words are within one edit of each other. 🚀
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.