isomorphic strings

fishercoder1534 · fishercoder1534 · commit 48f1bd058323 · 2016-10-27T22:11:51.000-07:00
diff --git a/EASY/src/easy/IsomorphicStrings.java b/EASY/src/easy/IsomorphicStrings.java
@@ -0,0 +1,27 @@
+package easy;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class IsomorphicStrings {
+    /**space should be O(1) since it only has alphabetic letters which are capped at 52.*/
+
+    public boolean isIsomorphic(String s, String t) {
+        if(s == null || s.length() == 0) return (t == null || t.length() == 0);
+        if(t == null || t.length() == 0) return (s == null || s.length() == 0);
+        char[] schar = s.toCharArray();
+        char[] tchar = t.toCharArray();
+        Map<Character, Character> map = new HashMap();
+        if(s.length() != t.length()) return false;
+        for(int i = 0; i < s.length(); i++){
+            if(map.containsKey(schar[i])){
+                if(map.get(schar[i]) != tchar[i]) return false;
+            } else {
+                if(map.containsValue(tchar[i])) return false;//this line is necessary for this case: ("ab", "aa")
+                map.put(schar[i], tchar[i]);
+            }
+        }
+        return true;
+    }
+
+}
diff --git a/README.md b/README.md
@@ -26,6 +26,7 @@
 |257|[Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/)|[Solution](../../blob/master/EASY/src/easy/BinaryTreePaths.java) | O(n*h) | O(h) | DFS/Recursion
 |209|[Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)|[Solution](../../blob/master/MEDIUM/src/medium/MinimumSizeSubarraySum.java)| O(n)|O(1) | Medium|
 |206|[Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)|[Solution](../../blob/master/EASY/src/easy/ReverseLinkedList.java)| O(n)|O(1) | Easy
+|205|[Isomorphic Strings](https://leetcode.com/problems/isomorphic-strings/)|[Solution](../../blob/master/EASY/src/easy/IsomorphicStrings.java)| O(n)|O(1) | Easy
 |200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Union Find](../../blob/master/MEDIUM/src/medium/NumberOfIslandsUnionFind.java) [DFS](../../blob/master/MEDIUM/src/medium/NumberofIslandsDFS.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
 |189|[Rotate Array](https://leetcode.com/problems/rotate-array/)|[Solution](../../blob/master/EASY/src/easy/RotateArray.java)| O(n)|O(n), could be optimized to O(1) | Easy
 |173|[Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)|[Queue](../../blob/master/MEDIUM/src/medium/BSTIterator_using_q.java) [Stack](../../blob/master/MEDIUM/src/medium/BSTIterator_using_stack.java)| O(1) |O(h) | Medium|
