beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: DP / 2D Table•Medium

Edit distance (Levenshtein)

Problem Intuition & Objective

Minimum insert/delete/replace operations to convert word1 to word2.

Time ComplexityO(m×n)
Optimal
Space ComplexityO(min(m,n))
Memory Bounds
Optimal Algorithmic Approach

2D DP. Base cases: dp[i][0]=i, dp[0][j]=j.

Core Invariants & Edge Cases

  • dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]
  • If chars match: dp[i][j] = dp[i-1][j-1]
  • Else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Previous ProblemLongest common subsequence (LCS)Next Problem Partition equal subset sum

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.