Edit Distance
Updated
Problem statement
Given two case-sensitive strings source and target, return the minimum number of single-character operations needed to transform source into target.
One operation may insert a character, delete a character, or replace a character. Every operation costs 1.
Function
editDistance(source: String, target: String) → intExamples
Example 1
source = "horse"target = "ros"return = 3Replace h with r, delete the second r, and delete e.
Example 2
source = "sea"target = "eat"return = 2Delete s and insert t at the end.
Example 3
source = ""target = "abc"return = 3Insert all three target characters.
Constraints
0 <= source.length, target.length <= 6- Both strings contain only English letters.
- Character comparisons are case-sensitive.
Similar questions at other companies
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Minimum Dictionary SegmentsGoogle · PHONE SCREENGoogle interview questions
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Wildcard Pattern MatchingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Maximum Crayon Removal ScoreWells Fargo · OAWells Fargo interview questions
- Shuffle a String by Swapping Tree ChildrenNutanix · OANutanix interview questions
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- Longest Palindromic SubstringSiemens · PHONE SCREEN
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions