Two strings are isomorphic if the characters in string1 can be mapped by the exact same character in string2. 2 different characters should not be mapped to the same character but a character may map to itself. the order of the characters should be& preserved.
For example in the string EGG
and ADD
String 1 | String 2 | |
E | -> | A |
G | -> | D |
G | -> | D |
Both string EGG
and ADD
are isomorphic since each character of String 1 has unique mapping with the character of String 2
In string wesome.org and wesome.org
String 1 | String 2 | |
W | -> | W |
E | -> | E |
S | -> | S |
O | -> | O |
M | -> | M |
E | -> | E |
. | -> | . |
O | -> | O |
R | -> | R |
G | -> | G |
both strings are isomorphic since each character is mapped to itself.
package org.wesome.dsalgo;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Isomorphic {
public static boolean isIsomorphic(String str1, String str2) {
// Two strings cannot be isomorphic if they have different lengths.
if (str1.length() != str2.length()) {
return false;
}
// map will store mappings of str1 chars to str2 chars.
Map<Character, Character> map = new HashMap<>();
// set to keep track of already mapped characters.
Set<Character> set = new HashSet<>();
for (int i = 0; i < str1.length(); i++) {
char char1 = str1.charAt(i);
char char2 = str2.charAt(i);
// If char1 has been encountered before:
if (map.containsKey(char1)) {
// Return false if first occurrence of char1 is mapped to a different character.
if (map.get(char1) != char2) {
return false;
}
}
// If char1 is encountered for the first time, it has not been mapped yet:
else {
// Return false if char2 is already mapped to some other char in str1
if (set.contains(char2)) {
return false;
}
// insert in the map, and the set.
map.put(char1, char2);
set.add(char2);
}
}
return true;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
public class IsomorphicTest {
@Test
void IsomorphicTest1() {
String string1 = "egg", string2 = "add";
Assertions.assertTrue(Isomorphic.isIsomorphic(string1, string2));
}
@Test
void IsomorphicTest2() {
String string1 = "paper", string2 = "title";
Assertions.assertTrue(Isomorphic.isIsomorphic(string1, string2));
}
@Test
void IsomorphicTest3() {
String string1 = "wesome.org", string2 = "wesome.org";
Assertions.assertTrue(Isomorphic.isIsomorphic(string1, string2));
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}