Algoritmo de Anagram en java

Me gustaría hacer un algoritmo de anagtwig pero este código no funciona. ¿Dónde está mi culpa? Por ejemplo, des y sed es un anagtwig, pero la salida no es un anagtwig. Mientras tanto, debo usar el método de cadena. no matriz. 🙂

public static boolean isAnagram(String s1 , String s2) { String delStr=""; String newStr=""; for(int i=0;i<s1.length();i++) { for(int j=0 ; j < s2.length() ; j++) { if(s1.charAt(i)==s2.charAt(j)) { delStr=s1.substring(i,i+1); newStr=s2.replace(delStr,""); } } } if(newStr.equals("")) return true; else return false; } 

Esto se puede hacer en tiempo lineal usando espacio constante . Aquí hay un pseudo-código para ayudarlo a comenzar:

 // Create new hashtable/hashmap to keep track of how many times each character // is being used character_map -> new hash map // Initial check. If lengths are not the same, they can't be anagrams. if s1.length != s2.length: throw exception "Not anagrams" // Add all characters from s1 to hashmap. Increment the value to keep track of // number of occurences foreach character c1 in s1: character_map[c1]++ // Iterate through all character in s2 and decrement count of each character. foreach character c2 in s2: character_map[c2]-- // If they are anagrams, each character should be at "0" count at the point. // If we come across a character that is not, it means that they are not anagrams foreach key k, value v in character_map: if v != 0: throw exception "Not anagrams" 

Este código no se ordena y, por lo tanto, se puede hacer usando bucles simples. El tiempo de ejecución general es O (n) y el espacio total es O (1), por lo que es la solución más rápida. La cantidad de elementos que puede tener en el mapa hash es constante (es decir, sabe cuántos elementos hay en su conjunto de alfabeto).

Una manera más fácil podría ser simplemente ordenar los caracteres en ambas cadenas y comparar si son iguales:

 public static boolean isAnagram(String s1, String s2){ // Early termination check, if strings are of unequal lengths, // then they cannot be anagrams if ( s1.length() != s2.length() ) { return false; } s1=s1.toLowerCase(); s2=s2.toLowerCase(); char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); Arrays.sort(c1); Arrays.sort(c2); String sc1 = new String(c1); String sc2 = new String(c2); return sc1.equals(sc2); } 

Personalmente, creo que es más legible que nested for-loops = p

Tiene una complejidad de tiempo de ejecución O (n log n) , donde n es la longitud de la cadena más larga.

Editar: esta no es la solución óptima. Vea la respuesta de @ aam1r para el enfoque más eficiente (es decir, lo que debería decir en una entrevista)

 if(s1.charAt(i)==s2.charAt(j)) delStr=s1.substring(i,i+1); newStr=s2.replace(delStr,""); 

Este código es una buena demostración de por qué siempre debe tener curly braces alrededor de su if , incluso si solo hay una sola statement. Su segunda tarea está realmente fuera de la if-condition , y siempre sucederá.

La mejor manera de verificar que dos cadenas sean Anagram es convertirlas a una matriz de caracteres (String#toCharArray) . Luego, Arrays.sort usando el método Arrays.sort . Y haz la comparación sobre ellos.


Actualizado : –

Si solo quiere usar métodos String , entonces no necesita un bucle nested allí. Puedes hacerlo con solo uno.

Aquí está el código modificado de los suyos:

 public static boolean isAnagram(String s1 , String s2){ if (s1.length() != s2.length()) { return false; } for(int i = 0; i < s2.length(); i++) { if( !s1.contains("" + s2.charAt(i))) { return false; } s1 = s1.replaceFirst("" + s2.charAt(i), ""); s2 = s2.replaceFirst("" + s2.charAt(i), ""); } return true; } 

No estoy seguro de lo que intenta hacer, pero estoy bastante seguro de que no funcionará (y se ejecuta en O(n^2) . Pruebe esto (que se ejecuta en O(n log n) ) en su lugar :

 public static boolean isAnagram(String s1, String s2){ if (s1.length() != s2.length()) return false; char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); Arrays.sort(c1); Arrays.sort(c2); for(int i = 0; i < c1.length; i++) { if(c1[i] != c2[i]) return false; } return true; } 

Lo que sería más eficiente es comparar las cadenas en orden ordenado.

 public static boolean isAnagram(String s1 , String s2) { return s1.length() == s2.length() && checkSum(s1) == checkSum(s2) && Arrays.equals(lettersSorted(s1), lettersSorted(s2)); } static long checkSum(String s) { long sqrSum = 0; for(int i = 0; i < s.length(); s++) { char ch = s.charAt(i); sqrSum += ch + (1L << ch); } } static char[] lettersSorted(String s) { char[] chars = s.toCharArray(); Arrays.sort(chars); return chars; } 

Este es un algoritmo O (N ln N), pero será O (N) en promedio si las cadenas generalmente no son anagtwigs.

La razón por la que no funciona:

Usando “des” y “sed” como ejemplo.

En la última iteración para la que coincide, evaluará:

 if(s1.charAt(i)==s2.charAt(j)) { delStr=s1.substring(i,i+1); newStr=s2.replace(delStr,""); } 

Que será: if (“s” == “s”)

Luego ingresará al bloque if y evaluará

 newStr = "sed".replace("s",""); 

que le dará “ed”, en lugar de una cadena vacía.

La moraleja de la historia es que siempre estás reemplazando personajes de s2 menos un personaje, que nunca estarán vacíos.

Usar String.replace () es malo de todos modos, ya que reemplazará todas las instancias del carácter de forma predeterminada. Con String.replace (), consideraría “sed” como un anagtwig de “seeeeeeed”. Haría mejor en utilizar String.replaceFirst ().

En cualquier caso, un punto de partida es hacer las siguientes modificaciones:

 String newStr = s2; ... // inside if block newStr = newStr.replaceFirst( delStr, "" ); 

A continuación se muestra un fragmento de código conciso que determina si dos cadenas son anagtwigs en una sola iteración de ambas cadenas, más una iteración final de una matriz de 256 elementos. Este enfoque evita la clasificación de los caracteres en las cadenas y la conversión a / desde matrices de cadenas / char mediante el registro de los recuentos de caracteres en una matriz de asignación.

 static boolean isAnagram(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); int[] charMap = new int[256]; for (int i = 0; i < n; i++) { char c1 = s1.charAt(i); charMap[c1]++; char c2 = s2.charAt(i); charMap[c2]--; } for (int i = 0; i < charMap.length; i++) { if (charMap[i] != 0) return false; } return true; } 

Este código básicamente incrementa y disminuye una ubicación de índice en una matriz correspondiente a un carácter. Si alguno de los elementos de la matriz no es cero al final de la iteración, hubo una cantidad desigual de incrementos y decrementos, y por lo tanto las cadenas contienen caracteres diferentes y no pueden ser anagtwigs entre sí.

Dado que este algoritmo itera las dos cadenas del mismo tamaño una vez, el tiempo de ejecución es O (n). La complejidad del espacio es O (1) ya que el charMap siempre es constante dependiendo de los requisitos del juego de caracteres.

simplemente asegúrate de que estás tratando de verificar si s1 es correcto un anagtwig de s2. Eso también significa que s2 es un anagtwig de s1. Así que simplemente ordenaría s1 y s2 y verificaría si son iguales.

 String string1 = "fdafdas"; String string2 = "fdwqkjl"; char[] chars = string1.toCharArray(); char[] chars2 = string2.toCharArray(); Arrays.sort(chars); Arrays.sort(chars2); string1 = new String(chars); string2 = new String(chars2); if (string1.equals(string2)) { //They are an anagram } 
 public boolean isAnagram(String a, String b) { boolean result = false; final String one = a.replaceAll("[\\s+\\W+]", "").toLowerCase(); final String two = b.replaceAll("[\\s+\\W+]", "").toLowerCase(); if (one.length() == two.length()) { final char[] oneArray = one.toCharArray(); final char[] twoArray = two.toCharArray(); Arrays.sort(oneArray); Arrays.sort(twoArray); result = Arrays.equals(oneArray, twoArray); } return result; } 

O (n) solución sin ningún tipo de clasificación y usando solo un mapa. También se agregó la verificación nula adecuada que falta en otras soluciones.

 public boolean isAnagram(String leftString, String rightString) { if (leftString == null || rightString == null) { return false; } else if (leftString.length() != rightString.length()) { return false; } Map occurrencesMap = new HashMap<>(); for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); int nrOfCharsInLeft = occurrencesMap.containsKey(charFromLeft) ? occurrencesMap.get(charFromLeft) : 0; occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); int nrOfCharsInRight = occurrencesMap.containsKey(charFromRight) ? occurrencesMap.get(charFromRight) : 0; occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(int occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

y una solución menos genérica, pero un poco más rápida:

 public boolean isAnagram(String leftString, String rightString) { if (leftString == null || rightString == null) { return false; } else if (leftString.length() != rightString.length()) { return false; } char letters[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; Map occurrencesMap = new HashMap<>(); for (char l : letters) { occurrencesMap.put(l, 0); } for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); Integer nrOfCharsInLeft = occurrencesMap.get(charFromLeft); occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); Integer nrOfCharsInRight = occurrencesMap.get(charFromRight); occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(Integer occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

Aquí hay un enfoque más simple que se basa principalmente en Java. El código completo está aquí https://github.com/rdsr/algorithms/blob/master/src/jvm/misc/AnagramsList.java (Tenga en cuenta que esto resuelve un problema relacionado por otro)

 class Anagram { Map anagram; Anagram(String s) { anagram = new HashMap(); for (final Character c : s.toCharArray()) { if (anagram.containsKey(c)) { anagram.put(c, 1 + anagram.get(c)); } else { anagram.put(c, 1); } } } @Override public int hashCode() { //.. elided } @Override public boolean equals(Object obj) { //.. elided } } public class Anagrams { public static void main(String[] args) { System.out.println(new Anagram("abc").equals(new Anagram("bac"))); } } 

Versión más rápida utilizando el método de vector de bits para subcadenas de anagtwigs

 public boolean isAnagram(String _source1, String _source2) { int flag = 0, char_index = 0, counter = 0; if(_source2.length() < _source1.length()){ return false; } char[] _stringchar = _source1.toCharArray(); char[] _tocheck = _source2.toCharArray(); for(char character : _stringchar) { char_index = character - 'a'; if((flag & (1 << char_index)) == 0) flag |= (1 << char_index); } for(char toCheckcChar : _tocheck) { char_index = toCheckcChar - 'a'; if((flag & (1 << char_index)) > 0) counter++; else counter = 0; if(counter == _source1.length()) return true; } return false; } 

La razón simple es porque la función reemplazar crea un nuevo objeto String . No hace nada con la cadena real (en su caso s2 ), porque en Java, las cadenas son finales por naturaleza. Como lo señala cmonkey, siempre está eliminando un carácter de su cadena s2, pero en realidad se crea un nuevo objeto String con 1 carácter menos, s2 permanece como está.

La forma más sencilla de hacerlo funcionar en su caso sería crear un nuevo objeto de cadena y asignarlo a usted mismo.

 { s2=s2.replace(delString,""); .... if(s2.empty()) return true; return false; } 

una vez que hice una prueba para la entrevista de trabajo sobre anagtwigs. Lo cargué en mi cuenta de github. El código java comprueba si un archivo de texto (con varias líneas) es un poema anagtwig o un texto anagtwig.

https://github.com/javocsoft/anagram_poem_checker

¡Espero eso ayude!

Adiós.

solo vea en la línea newStr = s2.replace (delStr, “”);

lo que estás haciendo aquí reemplazando un char en s2 y asignando de nuevo a newStr, significa que no estás cambiando nada en s2. Simplemente reemplace este código por debajo de uno, funcionará bien

newStr = newStr.replace (delStr, “”);

Me tomé un tiempo para escribir la lógica y escribir un código para verificar dos cadenas, si son anagtwigs o no. ¡Por supuesto con la ayuda de las respuestas anteriores! XD

 public static void main(String[] args) { Map char_map = new HashMap(); Map empty_map = new HashMap(); String a = "HelloP"; String b = "HePlol"; if (a.length() != b.length()) { System.out.println("false"); System.exit(0); } for (char c : a.toLowerCase().toCharArray()) { empty_map.put(c, 0); if (char_map.containsKey(c)) char_map.put(c, 1 + char_map.get(c)); else char_map.put(c, 1); } for (char c : b.toLowerCase().toCharArray()) if (char_map.containsKey(c)) char_map.put(c, char_map.get(c) - 1); System.out.println(char_map.equals(empty_map)); } 

Creo que esto funciona con complejidad O (2n)

 public static boolean isAnagram(String str1, String str2){ if(str1.length() != str2.length()){ return false;} int[] buffer = new int[256]; for(char ch : str1.toCharArray()){ buffer[ch]++; } for(char ch : str2.toCharArray()){ if(buffer[ch]==0) return false; buffer[ch] = (buffer[ch] > 0)?(buffer[ch] - 1 ): -1 ; } return true; } 

Esta es una implementación de Java que escribí para usar una matriz en lugar de una HashMap. Esto ahorra espacio, además de que las matrices son realmente rápidas.

 public static boolean anagram(String s, String t) { if (s.length() != t.length()) return false; int[] arr = new int[123]; for (char c : s.toCharArray()) arr[c]++; for (char c : t.toCharArray()) arr[c]--; for (int i : arr) if (i != 0) return false; return true; } 
 import java.util.Scanner; public class JavaProgram { public static void main(String[] input) { String str1, str2; int len, len1, len2, i, j, found=0, not_found=0; Scanner scan = new Scanner(System.in); System.out.print("Enter First String : "); str1 = scan.nextLine(); System.out.print("Enter Second String : "); str2 = scan.nextLine(); len1 = str1.length(); len2 = str2.length(); if(len1 == len2) { len = len1; for(i=0; i 
 public class Anagram { public boolean isAnagram( String left, String right) { if (left.length() == right.length()) { Map map = new HashMap<>(); char[] a = left.toCharArray(), b = right.toCharArray(); for (int i = 0; i < a.length; i++) { accumulate(map, a[i]); accumulate(map, b[i]); } for (char c : map.keySet()) { if (map.get(c) > 0) { return false; } } return true; } else { return false; } } private void accumulate( Map map, char key) { if (map.containsKey(key)) { map.put(key, Math.abs(map.get(key) - 1)); } else { map.put(key, 1); } } } 

Aquí está mi solución desde tu aspecto

 private static boolean isAnagram(String s1, String s2){ int count = 0; boolean flag = false; if(s1.length() != s2.length()){ return false; } //checks whether both word's letters are the same for (int i = 0; i < s1.length(); i++){ for (int j = 0; j < s2.length(); j++){ if(s1.charAt(i) == s2.charAt(j)){ count++; break; } } } //if count equals to one of the Strings length then it is an anagram if(count == s2.length() ){ flag = true; } return flag; } 
  String str1="Mother In Law"; String str2="Hitler Woman"; char[] anag1=str1.replaceAll("\\s", "").toLowerCase().toCharArray(); char[] anag2=str2.replaceAll("\\s", "").toLowerCase().toCharArray(); Arrays.sort(anag1); Arrays.sort(anag2); System.out.println(Arrays.equals(anag1, anag2)? "words are anagrams":"words are not anagrams"); 

Supongo que la siguiente solución tiene O(n) complejidad, avíseme si alguien difiere.

 import java.util.HashMap; import java.util.Scanner; public class Anagrams { static boolean isAnagram(String word1, String word2) { if(word1.length() != word2.length()) { return false; } int flag=0; HashMap table = new HashMap(); for(int i=0; i< word1.length();i++) { table.put(word1.charAt(i),1); } for(int i=0; i< word2.length();i++) { if(table.containsKey(word2.charAt(i))) { continue; } else { flag=1; break; } } return flag == 0; } public static void main(String[] args) { System.out.println("Enter your string"); Scanner sc= new Scanner(System.in); String word1= sc.nextLine(); String word2=sc.nextLine(); boolean result = isAnagram(word1,word2); if(result) { System.out.println("The words are Anagrams"); } else{ System.out.println("The words are not Anagrams"); } } } 
 public static boolean isAnagram(String s1, String s2) { boolean aux = true; if (s1.length() != s2.length()){ aux = false; }else{ for (int i = 0; i < s1.length(); i++) if(s2.toUpperCase().indexOf(s1.toUpperCase().substring(i, i+1)) == -1) aux = false; } return aux; } 
 import java.util.*; class Anagrams { public static void main(String[] args) { System.out.println("Enter the two words"); Scanner scan = new Scanner(System.in); String word1 = scan.next(); String word2=scan.next(); StringBuilder sb1= new StringBuilder(word1); StringBuilder sb2= new StringBuilder(word2); int count=0; System.out.println("length ! "+sb1.length()); System.out.println("Length ! "+sb2.length()); if(sb1.length()==sb2.length()){ for(int i=0;i