萊文斯坦距離（Levenshtein Distance）是一種用於衡量兩個字元串之間相似度的算法，它定義了將一個字元串轉換成另一個字元串所需的最少編輯操作次數。這些編輯操作包括插入、刪除和替換字元。萊文斯坦距離以俄羅斯科學家Vladimir Levenshtein的名字命名，他在1965年提出了這個算法。
萊文斯坦距離的計算通常使用動態規劃算法，其時間複雜度和空間複雜度均為O(mn)，其中m和n分別是兩個字元串的長度。
萊文斯坦距離具有以下性質：
非負性：距離越大，表示兩個字元串之間的差異越大。
對稱性：萊文斯坦距離滿足對稱性，即D(A, B) = D(B, A)，其中D(A, B)表示字元串A和B之間的萊文斯坦距離。
三角不等式：對於任意三個字元串A、B和C，D(A, C) ≤ D(A, B) + D(B, C)，這意味著從A到C的距離不大於從A到B和從B到C的距離之和。
最小編輯操作序列：萊文斯坦距離可以用來找出將一個字元串轉換成另一個字元串的最小編輯操作序列。
例如，字元串「kitten」和「sitting」之間的萊文斯坦距離是3。將「kitten」變為「sitting」的最小處理方式如下：「kitten」→「sitten」（將「k」改為「s」）→「sitten」（將「e」改為「i」）→「sitting」（最後加入「g」）。
萊文斯坦距離的套用場景包括搜尋詞糾錯、DNA分析、語音識別、抄襲檢測等。