One Edit Distance: Accepted

gouthampradhan · gouthampradhan · commit e3b976b929c5 · 2017-12-09T21:03:42.000+01:00
diff --git a/README.md b/README.md
@@ -201,6 +201,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Permutation in String](problems/src/string/PermutationInString.java) (Medium)
 - [Add Binary](problems/src/string/AddBinary.java) (Easy)
 - [Valid Palindrome II](problems/src/string/ValidPalindromeII.java) (Easy)
+- [One Edit Distance](problems/src/string/OneEditDistance.java) (Medium)
 
 #### [Tree](problems/src/tree)
 
diff --git a/problems/src/string/OneEditDistance.java b/problems/src/string/OneEditDistance.java
@@ -0,0 +1,51 @@
+package string;
+
+/**
+ * Created by gouthamvidyapradhan on 09/12/2017.
+ *
+ * Given two strings S and T, determine if they are both one edit distance apart.
+ */
+public class OneEditDistance {
+
+    /**
+     * Main method
+     * @param args
+     * @throws Exception
+     */
+    public static void main(String[] args) throws Exception{
+        System.out.println(new OneEditDistance().isOneEditDistance("abxd", "adxb"));
+    }
+
+    public boolean isOneEditDistance(String s, String t) {
+        if(Math.abs(s.length() - t.length()) > 1 || s.equals(t)) return false;
+        if(s.length() > t.length()){
+            return hasDiffOne(s, t, false);
+        } else if(t.length() > s.length()){
+            return hasDiffOne(t, s, false);
+        } else{
+            return hasDiffOne(s, t, true);
+        }
+    }
+
+    private boolean hasDiffOne(String s, String t, boolean sameLength){
+        int count = 0, i = 0, j = 0;
+        for(int l1 = s.length(), l2 = t.length(); i < l1 && j < l2;){
+            if(s.charAt(i) == t.charAt(j)){
+                i++; j++;
+            } else{
+                if(count > 0) return false;
+                count++;
+                if(sameLength){
+                    i++; j++;
+                } else{
+                    i++;
+                }
+            }
+        }
+        if(i == j){
+            return true;
+        } else{
+            return (s.charAt(s.length() - 1) == t.charAt(t.length() - 1));
+        }
+    }
+}
