import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Given two strings s and t, determine if they are isomorphic.
 * <p>
 * Two strings are isomorphic if the characters in s can be replaced to get t.
 * <p>
 * All occurrences of a character must be replaced with another character while preserving the order of characters. No
 * two characters may map to the same character but a character may map to itself.
 * <p>
 * For example,
 * Given "egg", "add", return true.
 * <p>
 * Given "foo", "bar", return false.
 * <p>
 * Given "paper", "title", return true.
 * <p>
 * Note:
 * You may assume both s and t have the same length.
 * <p>
 * Tags: Hash Table
 * Similar Problems: (E) Word Pattern
 */
public class IsomorphicStrings {

    private IsomorphicStrings is;

    /**
     * Store the last seen positions of current (i-th) characters in both strings.
     */
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null) return false;
        int[] m = new int[512];
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (m[s.charAt(i)] != m[t.charAt(i) + 256]) return false;
            m[s.charAt(i)] = m[t.charAt(i) + 256] = i + 1;
        }
        return true;
    }

    @Before
    public void setUp() {
        is = new IsomorphicStrings();
    }

    @Test
    public void testEdgeCases() {
        Assert.assertFalse(is.isIsomorphic(null, null));
        Assert.assertFalse(is.isIsomorphic(null, ""));
        Assert.assertFalse(is.isIsomorphic("", null));
        Assert.assertTrue(is.isIsomorphic("", ""));
    }

    @Test
    public void testExamples() {
        // "egg", "add", return true
        Assert.assertTrue(is.isIsomorphic("egg", "add"));
        // "foo", "bar", return false
        Assert.assertFalse(is.isIsomorphic("foo", "bar"));
        // "paper", "title", return true
        Assert.assertTrue(is.isIsomorphic("paper", "title"));
        // "papper", "tittle", return true
        Assert.assertTrue(is.isIsomorphic("papper", "tittle"));
        // "abba", "abab"
        Assert.assertFalse(is.isIsomorphic("abba", "abab"));
    }

    @After
    public void tearDown() {
        is = null;
    }

}

@@ -1,24 +1,74 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0A
 import org.junit.After;%0A
@@ -726,24 +726,50 @@
 gth.%0A * %3Cp%3E%0A
+ * Company Tags: LinkedIn%0A
  * Tags: Has
@@ -906,82 +906,255 @@
   * 
-Store the last seen positions of current (i-th) characters in both strings
+Hash Table.%0A     * Store the previous seen index of a character. 0 means not seen yet.%0A     * If the last seen indices are different, return false.%0A     * Update index to i + 1.%0A     * After the check, return true, since s and t are of same length
 .%0A  
@@ -1248,16 +1248,30 @@
 == null)
+ %7B%0A           
  return 
@@ -1269,32 +1269,42 @@
   return false;%0A
+        %7D%0A
         int%5B%5D m 
@@ -1323,38 +1323,8 @@
 2%5D;%0A
-        int len = s.length();%0A
     
@@ -1347,19 +1347,26 @@
  0; i %3C 
+s.
 len
+gth()
 ; i++) %7B
@@ -1422,29 +1422,61 @@
 + 256%5D) 
-return false;
+%7B%0A                return false;%0A            %7D
 %0A       

update isomorphic strings