Watch 10 video solutions for One Edit Distance, a medium level problem involving Two Pointers, String. This walkthrough by Tushar Roy - Coding Made Simple has 571,776 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
s to get t.s to get t.s with a different character to get t.
Example 1:
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step.
Constraints:
0 <= s.length, t.length <= 104s and t consist of lowercase letters, uppercase letters, and digits.Problem Overview: You are given two strings s and t. The goal is to determine whether they are exactly one edit apart. An edit can be an insertion, deletion, or replacement of a single character. If zero edits or more than one edit are required, the answer should be false.
Approach 1: Edit Distance Dynamic Programming (O(m*n) time, O(m*n) space)
A straightforward solution computes the classic edit distance between the two strings using dynamic programming. Create a DP table where dp[i][j] represents the minimum number of edits required to convert the first i characters of s into the first j characters of t. Each state considers insertion, deletion, or replacement. After filling the table, check whether the final edit distance equals exactly 1. This approach is simple and reusable for general edit distance problems, but it performs unnecessary work because the problem only cares about distance one. Time complexity is O(m*n) and space complexity is O(m*n), where m and n are the string lengths.
Approach 2: Discuss Different Cases with Two Pointers (O(n) time, O(1) space)
The optimal solution relies on careful case analysis and a linear scan using two pointers. First check the length difference. If the absolute difference exceeds one, the strings cannot be one edit apart. Otherwise iterate through both strings until the first mismatch appears. At that point three scenarios are possible: replacement when the lengths are equal, insertion into the shorter string, or deletion from the longer string. Instead of performing an explicit edit, advance the pointers according to the case and verify that the remaining substrings match.
This approach works because only one edit is allowed. Once a mismatch occurs, the rest of the characters must align perfectly. If no mismatch appears during the scan, the strings are one edit apart only when their lengths differ by exactly one (an extra trailing character). The algorithm processes each character once, giving O(n) time complexity and constant O(1) space. The logic relies heavily on careful pointer movement and efficient string comparison.
Recommended for interviews: Interviewers expect the linear two-pointer approach. The dynamic programming method demonstrates understanding of general edit distance, but it is overkill for this constraint. Showing the DP idea briefly and then optimizing to the case-based two pointer scan signals strong problem-solving ability and awareness of time complexity tradeoffs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Edit Distance Dynamic Programming | O(m*n) | O(m*n) | When solving the general edit distance problem or when multiple edits must be computed |
| Case Analysis with Two Pointers | O(n) | O(1) | Best for checking if two strings differ by exactly one edit |