/161. One Edit Distance
Previous|Next

161. One Edit Distance

Medium
Two Pointers34.6% acceptance

Given two strings, determine if they are exactly one edit distance apart. An edit is defined as inserting, deleting, or replacing a single character.

Example 1

Input: str_a = abcde, str_b = abfde

Output: True

Explanation: One replacement: c -> f.

Example 2

Input: str_a = xyz, str_b = xy

Output: True

Explanation: One deletion: remove z from str_a.

Example 3

Input: str_a = hello, str_b = helloo

Output: True

Explanation: One insertion: add o to str_a.

Example 4

Input: str_a = test, str_b = test

Output: False

Explanation: No edits needed.

Example 5

Input: str_a = abc, str_b = adc

Output: True

Explanation: One replacement: b -> d.

Constraints

  • 1 <= len(str_a) <= 10000
  • 1 <= len(str_b) <= 10000
  • str_a and str_b consist of lowercase English letters
Python (current runtime)

Case 1

Input: str_a = 'abcd', str_b = 'abed'

Expected: True

Case 2

Input: str_a = 'a', str_b = 'ab'

Expected: True

Case 3

Input: str_a = 'abcdef', str_b = 'abcxef'

Expected: True

Case 4

Input: str_a = 'abc', str_b = 'ab'

Expected: True

Case 5

Input: str_a = 'abc', str_b = 'abcd'

Expected: True

Case 6

Input: str_a = 'abc', str_b = 'axc'

Expected: True

Case 7

Input: str_a = 'abc', str_b = 'abx'

Expected: True

Case 8

Input: str_a = 'abc', str_b = 'axbc'

Expected: False

Case 9

Input: str_a = 'abc', str_b = 'abcde'

Expected: False