الگوریتم‌ها (انیمیشن)در مرورگر شما اجرا می‌شودتاریخ بررسی: ۹ میزان ۱۴۰۵

Levenshtein Distance (Fuzzy Search): انیمیشن

Levenshtein Distance (Fuzzy Search): انیمیشن. الگوریتم‌های متحرک برای فرانت‌اند: مرتب‌سازی، جستجو، debounce و throttle، حلقه‌ی رویداد، DOM مجازی، حافظه‌ی نهان، trie و مسیریابی. سریع، خصوصی و آسان در مرورگر شما.

محلیبه‌طور پیش‌فرض خصوصیسریعبدون ثبت‌نام

دکمه‌ها و متن‌های ابزار پایین فعلاً به انگلیسی است.

Graphs and textTime: O(m × n)Space: O(m × n)

Word 1Word 2

		s	i	t	t	i	n	g

k
i
t
t
e
n

Step 1 / 45

Levenshtein distance counts the fewest single-letter edits (insert, delete, replace) to turn "kitten" into "sitting". It powers typo-tolerant ("fuzzy") search.

JavaScript

1function levenshtein(a, b) {
2  const dp = Array.from({ length: a.length + 1 }, (_, i) => [i]);
3  for (let j = 1; j <= b.length; j++) dp[0][j] = j;
4  for (let i = 1; i <= a.length; i++) {
5    for (let j = 1; j <= b.length; j++) {
6      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
7      dp[i][j] = Math.min(
8        dp[i - 1][j] + 1,
9        dp[i][j - 1] + 1,
10        dp[i - 1][j - 1] + cost
11      );
12    }
13  }
14  return dp[a.length][b.length];
15}

Tip: use the arrow keys to step and the space bar to play or pause.

Loading animation...