Java

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

  1. Consider a mapping table that maps each character in the first string to a single character in the second string.
  2. Consider a mappedBefore database that keeps track of each char from the second string that is already linked to a char from the first.
  3. One by one, read the first string’s characters.
  4. Get the mapping for the read char from the first string if it’s in the mapping table.
  5. Take the char from the second string that is related.
  6. Return false if the mapping and the read char from the second string are not the same.
  7. 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.
  8. Otherwise, add the first table’s read char and the second table’s read char to the mapping table.
  9. Continue on to step 3 if you haven’t already.
  10. 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;

}

}

RECOMMENDED ARTICLES





Leave a Reply

Your email address will not be published.