You are coding as a Guest. Sign in with your RoleNest account to permanently track your streak, earn XP, and climb the Campus Leaderboard!
Sign In with RoleNestProblem Set
🔥Edit Distance: Levenshtein Matrix DPHard
SUPER HARD PROBLEM OF THE DAY+150 XP • FAANG OA TIER
High-difficulty challenge matching authentic Google, Amazon & Uber L5 online assessment conditions.
HardDynamic Programming•Acceptance: 56.2%
Edit Distance: Levenshtein Matrix DP
Targeted in FAANG & Tech OA:GoogleUberAmazon
Real-World Engineering Context
Underpins fuzzy search and query autocorrect in Google Search, spellcheckers, and DNA sequence genome alignment algorithms.
Given two strings `word1` and `word2`, return the minimum number of operations required to convert `word1` to `word2`.
You have the following three operations permitted on a word:
1. Insert a character
2. Delete a character
3. Replace a character
Sample Test Cases
Input: ["horse","ros"]
Expected: 3
Input: ["intention","execution"]
Expected: 5
Input: ["same","same"]
Expected: 0
Constraints
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
Recruiter Fast-Track ReferralVerified Candidate
Direct pipeline to Google, Amazon, Microsoft, Swiggy, & Uber recruiters
Top DevScore profiles bypass resume screening filters. Every verified problem solve writes authentic proof-of-work to your profile and dispatches you directly into employer inboxes on RoleNest.
Explore 5,000+ Direct ATS Openings on RoleNest ↗✓ Direct Referral Active
Language:
Ready to test. Click Run Code or Submit Solution to run test cases in isolated browser sandbox.