Dadas dos cadenas s y t, determina si son isomórficas. Dos cadenas son isomorfas si los caracteres de s se pueden reemplazar para obtener t.
Por ejemplo, «egg» y «add» son isomorfos, «foo» y «bar» no lo son.
Solución Java 1
Podemos definir un mapa que rastrea las asignaciones char-char. Si un valor ya está asignado, no se puede volver a asignar.
public boolean isIsomorphic(String s, String t) { if(s.length()!=t.length()){ return false; } HashMap<Character, Character> map1 = new HashMap<>(); HashMap<Character, Character> map2 = new HashMap<>(); for(int i=0; i<s.length(); i++){ char c1 = s.charAt(i); char c2 = t.charAt(i); if(map1.containsKey(c1)){ if(c2!=map1.get(c1)){ return false; } }else{ if(map2.containsKey(c2)){ return false; } map1.put(c1, c2); map2.put(c2, c1); } } return true; } |
La complejidad del tiempo es O (n) y la complejidad del espacio es O (n), donde n es la longitud de la cadena de entrada.
Solución Java 2
También podemos simplemente verificar si un valor se asigna dos veces al verificar el número de elementos únicos.
public boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) { return false; } HashMap<Character, Character> map = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c1 = s.charAt(i); char c2 = t.charAt(i); if (map.containsKey(c1)) { if (map.get(c1) != c2) { return false; } } else { map.put(c1, c2); } } HashSet<Character> set = new HashSet<>(map.values()); if (set.size() == map.values().size()) { return true; } return false; } |
