161. One Edit Distance
Given two strings s and t, determine if they are both one edit distance apart.
Note:
There are 3 possiblities to satisify one edit distance apart:
- Insert a character into s to get t
- Delete a character from s to get t
- Replace a character of s 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 = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get t.---
Related problems
---
Intuition
Corner cases when strings are null and 0 length
dfs(i, j, moves)
if (moves > 2) => return false
if chars are same => dfs(i + 1, j + 1, moves)
else dfs(i, j + 1, moves + 1) || dfs(i + 1, j + 1, moves + 1)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| /** | |
| * @param s: a string | |
| * @param t: a string | |
| * @return: true if they are both one edit distance apart or false | |
| */ | |
| public boolean isOneEditDistance(String s, String t) { | |
| if (s.length() > t.length()) { | |
| return isOneEditDistance(t, s); | |
| } | |
| if (Math.abs(s.length() - t.length()) > 1) { | |
| return false; | |
| } | |
| boolean oneEdit = false; | |
| int i, j; | |
| for (i = 0, j = 0; i < s.length() && j < t.length(); i++, j++) { | |
| if (s.charAt(i) == t.charAt(j)) { | |
| continue; | |
| } else { | |
| if (oneEdit) { | |
| return false; | |
| } | |
| oneEdit = true; | |
| if (s.length() != t.length()) { | |
| j++; | |
| } | |
| } | |
| } | |
| return s.length() == t.length() ? oneEdit : true; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| /** | |
| * @param s: a string | |
| * @param t: a string | |
| * @return: true if they are both one edit distance apart or false | |
| */ | |
| public boolean isOneEditDistance(String s, String t) { | |
| if (s.equals(t) || Math.abs(s.length() - t.length()) > 1) { | |
| return false; | |
| } | |
| // shorter string first | |
| if (s.length() <= t.length()) | |
| return dfs(s, t, 0, 0, 0); | |
| else | |
| return dfs(t, s, 0, 0, 0); | |
| } | |
| private boolean dfs(String s, String t, int i, int j, int edits) { | |
| if (edits > 1) { | |
| return false; | |
| } | |
| if (i == s.length()) { | |
| return j == t.length() || edits < 2; | |
| } | |
| if (s.charAt(i) == t.charAt(j)) { | |
| return dfs(s, t, i + 1, j + 1, edits); | |
| } else { | |
| return dfs(s, t, i + 1, j + 1, edits + 1) || dfs(s, t, i, j + 1, edits + 1); | |
| } | |
| } | |
| } |
