Алгоритмдер (анимация)Браузеріңізде жұмыс істейдіТексерілген күні: 2026 ж. 1 қазан

Levenshtein Distance (Fuzzy Search): анимация

Levenshtein Distance (Fuzzy Search): анимация. Фронтенд үшін анимациялы алгоритмдер: сұрыптау, іздеу, debounce және throttle, event loop, виртуалды 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...