Class LevenshteinDistance

java.lang.Object

cloud.opencode.base.string.similarity.LevenshteinDistance

public final class LevenshteinDistance
extends Object

Levenshtein Distance - Calculates edit distance between strings. 编辑距离 - 计算字符串之间的编辑距离。

Features | 主要功能:

• Edit distance calculation - 编辑距离计算
• Similarity ratio calculation - 相似度比率计算
• O(n*m) time, O(m) space optimized - O(n*m)时间，O(m)空间优化

Usage Examples | 使用示例:

int distance = LevenshteinDistance.calculate("kitten", "sitting"); // 3
double similarity = LevenshteinDistance.similarity("hello", "hallo"); // 0.8

Security | 安全性:

• Thread-safe: Yes (stateless utility) - 线程安全: 是（无状态工具类）
• Null-safe: No (throws IllegalArgumentException for null) - 空值安全: 否

Since:

JDK 25, opencode-base-string V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

• OpenCode.cloud

Method Summary

Modifier and Type	Method	Description
static int	boundedDistance(String s1, String s2, int threshold)	Bounded Levenshtein distance with early termination.
static int	calculate(String s1, String s2)
static double	similarity(String s1, String s2)

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

calculate

public static int calculate(String s1,
 String s2)

boundedDistance

public static int boundedDistance(String s1,
 String s2,
 int threshold)

Bounded Levenshtein distance with early termination. 带阈值的有界Levenshtein距离，提前终止。

Returns the edit distance if <= threshold, otherwise -1. Uses a banded DP algorithm that only computes a diagonal strip of width 2*threshold+1, achieving O(min(m,n)*threshold) time.

如果编辑距离 <= threshold 则返回距离，否则返回 -1。 使用带状DP算法，只计算对角线附近 2*threshold+1 宽度的区域， 时间复杂度为 O(min(m,n)*threshold)。

Examples | 示例:

boundedDistance("kitten", "sitting", 3) = 3
boundedDistance("kitten", "sitting", 2) = -1
boundedDistance("abc", "abc", 0)        = 0

Performance | 性能:

Time: O(min(m,n) * threshold), Space: O(min(m,n))

Parameters:

s1 - the first string | 第一个字符串

s2 - the second string | 第二个字符串

threshold - the maximum acceptable distance | 最大可接受距离

Returns:

the edit distance if <= threshold, otherwise -1 | 如果编辑距离 <= threshold 则返回距离，否则返回 -1

Throws:

IllegalArgumentException - if either string is null or threshold is negative | 如果字符串为null或阈值为负数

similarity

public static double similarity(String s1,
 String s2)