Wszystko Nowy

user:thomas Gisty stworzone przez użytkownika

title:mygist Gisty z podanym tytułem

filename:myfile.txt Gisty zawierające pliki z podanym tytułem

extension:yml Gisty zawierające pliki z podanym rozszerzeniem

language:go Gisty zawierające pliki z podanym językiem

topic:homelab gists with given topic

Zarejestruj się

Zaloguj się

Wszystko Nowy Zarejestruj się Zaloguj się

linkjobai

Dołączono 5 days ago

Ostatnio utworzono
Najdawniej utworzono
Ostatnio zaktualizowano
Najdawniej zaktualizowano
Wszystkie Gisty 1

linkjobai / Edit Distance: A Dynamic Programming Walkthrough

0 polubień
0 forków
1 plików
Ostatnio aktywne 5 days ago
Interview prep notes
interview

Edit Distance: A Dynamic Programming Walkthrough

Edit Distance (LeetCode 72) asks for the minimum number of insertions, deletions and substitutions that turn one word into another. It's the textbook two-string DP and a good template for many others.

Define the state

dp[i][j] = minimum edits to turn the first i characters of a into the first j characters of b.

  • If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1].
  • Otherwise: 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)).
Nowsze Starsze

Obsługiwane przez Opengist ⋅ Load: 34ms⋅

Polski
Čeština Deutsch English Español Français Magyar Italiano 日本語 Polski Português Русский Türkçe Українська 中文 繁體中文