[LeetCode] 161. One Edit Distance
Given two strings S and T, determine if they are both one edit distance apart.
Thought process:
Check if S and T are one insertion or replacement away.
Solution:
Time complexity: O(n).
Thought process:
Check if S and T are one insertion or replacement away.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | class Solution { public boolean isOneEditDistance(String s, String t) { if (s.equals(t)) { return false; } return isOneInsert(s, t) || isOneReplace(s, t); } private boolean isOneInsert(String s, String t) { if (Math.abs(s.length() - t.length()) != 1) { return false; } boolean inserted = false; int i = 0; int j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) != t.charAt(j)) { if (inserted) { return false; } inserted = true; if (s.length() < t.length()) { j++; } else { i++; } } else { i++; j++; } } return true; } private boolean isOneReplace(String s, String t) { if (s.length() != t.length()) { return false; } boolean replaced = false; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != t.charAt(i)) { if (replaced) { return false; } replaced = true; } } return true; } } |
Time complexity: O(n).
Comments
Post a Comment