One edit distance

Two Pointers String

34.6% acceptance

Mar 31, 2026

1447

194

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false. A string s is said to be one distance apart from a string t if you can: Insert exactly one character into s to get t. Delete exactly one character from s to get t. Replace exactly one character of s with a different character to get t.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_one_edit_distance(s: String, t: String) -> bool {
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let (ns, nt) = (s.len(), t.len());
    if ns > nt {
      return Self::is_one_edit_distance_bytes(t, s);
    }
    let diff = nt - ns;
    if diff > 1 {
      return false;
    }
    for i in 0..ns {
      if s[i] != t[i] {
        if diff == 0 {
          return s[i + 1..] == t[i + 1..];
        } else {
          return s[i..] == t[i + 1..];
        }
      }
    }
    diff == 1
  }

  fn is_one_edit_distance_bytes(s: &[u8], t: &[u8]) -> bool {
    let (ns, nt) = (s.len(), t.len());
    let diff = nt - ns;
    if diff > 1 {
      return false;
    }
    for i in 0..ns {
      if s[i] != t[i] {
        if diff == 0 {
          return s[i + 1..] == t[i + 1..];
        } else {
          return s[i..] == t[i + 1..];
        }
      }
    }
    diff == 1
  }
}