C# 字符串相似度计算实现莱文斯坦距离算法及代码示例

莱文斯坦距离（Levenshtein Distance）算法是一种计算字符串相似度的常用方法。该算法的核心思想是，通过最少的编辑操作（包括替换、插入、和删除）将一个字符串转换为另一个字符串，从而得出两个字符串之间的“距离”。莱文斯坦距离适用于多个场景，如拼写检查、DNA序列分析、文本相似度评估等。以下是实现莱文斯坦距离的C#代码示例，帮助您快速在C#项目中应用此算法。

public static int LevenshteinDistance(string a, string b) 
{
    int[,] dp = new int[a.Length + 1, b.Length + 1];

    for (int i = 0; i <= a.Length; i++) 
    {
        dp[i, 0] = i;
    }

    for (int j = 0; j <= b.Length; j++) 
    {
        dp[0, j] = j;
    }

    for (int i = 1; i <= a.Length; i++) 
    {
        for (int j = 1; j <= b.Length; j++) 
        {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i, j] = Math.Min(
                Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1),
                dp[i - 1, j - 1] + cost
            );
        }
    }

    return dp[a.Length, b.Length];
}

代码解析

1. 动态规划二维数组 dp[i, j]：存储将字符串a的前i个字符转换成字符串b的前j个字符所需的最少编辑次数。
2. 初始状态：第1行和第1列的填充，表示从空字符串到目标字符串所需的插入次数。
3. 状态转移方程：每个字符匹配时计算替换、插入、删除的最小次数，形成最终矩阵。

示例

假设字符串 a = "kitten" 和 b = "sitting"，调用 LevenshteinDistance(a, b) 将返回3，表示将"kitten"转换为"sitting"所需的最少操作次数为3（替换、插入、替换各一次）。

小贴士：在较长字符串比较中，为提升效率，可进一步优化算法，如使用滚动数组或其他矩阵压缩技巧。