What is Isomorphic Strings
Specification
Determine whether two strings, s and t, are isomorphic.
If the characters in s can be replaced to get t, two strings are isomorphic.
All instances of a character must be replaced with another character while maintaining the character order. A character can map to itself, but no two characters can map to each other.
Examples:
Example 1:
Input: s = “egg”, t = "add"
Output: true
Example 2:
Input: s = "foo", t = "bar"
Output: false
Example 3:
Input: s = "paper", t = "title"
Output: true
Algorithm
- Consider a mapping table that maps each character in the first string to a single character in the second string.
- Consider a mappedBefore database that keeps track of each char from the second string that is already linked to a char from the first.
- One by one, read the first string’s characters.
- Get the mapping for the read char from the first string if it’s in the mapping table.
- Take the char from the second string that is related.
- Return false if the mapping and the read char from the second string are not the same.
- Else Read the relevant char from the second string if the read char from the first string does not exist in the mapping table; if the char exists in the mappedBefore table, return false.
- Otherwise, add the first table’s read char and the second table’s read char to the mapping table.
- Continue on to step 3 if you haven’t already.
- True should be returned.
Code:
import java.util.*;
public class ShapeEquivalanceCheckerS2 implements ShapeEquivalanceChecker {
Map mapping;
Map mappedBefore;
boolean equivalent;
@Override
public boolean isIsomorphic(String s, String t) {
mapping = new HashMap ();
mappedBefore = new HashMap ();
equivalent = true;
for (int i = 0; i < s.length(); i++)
{
if (mapping.containsKey(s.charAt(i)))
{
char mapped = mapping.get(s.charAt(i));
if (mapped != t.charAt(i))
{
equivalent = false;
break;
}
}
else
{
if (mappedBefore.containsKey(t.charAt(i)))
{
equivalent = false;
break;
}
else
{
mappedBefore.put(t.charAt(i), true);
mapping.put(s.charAt(i), t.charAt(i));
}
}
}
return equivalent;
}
}