java - codigo - anagrama en netbeans

Cómo verificar si dos palabras son anagramas

Question

Tengo un programa que te muestra si dos palabras son anagramas el uno del otro. Hay algunos ejemplos que no funcionarán correctamente y agradecería cualquier ayuda, aunque si no fuera avanzado, sería genial, ya que soy un programador de primer año. "schoolmaster" y "theclassroom" son anagramas entre sí, sin embargo, cuando cambio "theclassroom" a "theclafsroom" todavía dice que son anagramas, ¿qué estoy haciendo mal?

import java.util.ArrayList;
public class AnagramCheck
{
public static void main(String args[])
{
String phrase1 = "tbeclassroom";
phrase1 = (phrase1.toLowerCase()).trim();
char[] phrase1Arr = phrase1.toCharArray();
String phrase2 = "schoolmaster";
phrase2 = (phrase2.toLowerCase()).trim();
ArrayList<Character> phrase2ArrList = convertStringToArraylist(phrase2);
if (phrase1.length() != phrase2.length())
{
System.out.print("There is no anagram present.");
}
else
{
boolean isFound = true;
for (int i=0; i<phrase1Arr.length; i++)
{
for(int j = 0; j < phrase2ArrList.size(); j++)
{
if(phrase1Arr[i] == phrase2ArrList.get(j))
{
System.out.print("There is a common element./n");
isFound = ;
phrase2ArrList.remove(j);
}
}
if(isFound == false)
{
System.out.print("There are no anagrams present.");
return;
}
}
System.out.printf("%s is an anagram of %s", phrase1, phrase2);
}
}
public static ArrayList<Character> convertStringToArraylist(String str) {
ArrayList<Character> charList = new ArrayList<Character>();
for(int i = 0; i<str.length();i++){
charList.add(str.charAt(i));
}
return charList;
}
}

Answer 1

¡Funciona perfectamente! But not a good approach because it runs in O(n^2)

boolean isAnagram(String A, String B) {
if(A.length() != B.length())
return false;
A = A.toLowerCase();
B = B.toLowerCase();
for(int i = 0; i < A.length(); i++){
boolean found = false;
for(int j = 0; j < B.length(); j++){
if(A.charAt(i) == B.charAt(j)){
found = true;
break;
}
}
if(!found){
return false;
}
}
for(int i = 0; i < B.length(); i++){
boolean found = false;
for(int j = 0; j < A.length(); j++){
if(A.charAt(j) == B.charAt(i)){
found = true;
break;
}
}
if(!found){
return false;
}
}
int sum1 = 0, sum2 = 0;
for(int i = 0; i < A.length(); i++){
sum1 += (int)A.charAt(i);
sum2 += (int)B.charAt(i);
}
if(sum1 == sum2){
return true;
}
return false;
}

Answer 2

Al usar más memoria (un HashMap de como máximo N / 2 elementos) no necesitamos ordenar las cadenas.

public static boolean areAnagrams(String one, String two) {
if (one.length() == two.length()) {
String s0 = one.toLowerCase();
String s1 = two.toLowerCase();
HashMap<Character, Integer> chars = new HashMap<Character, Integer>(one.length());
Integer count;
for (char c : s0.toCharArray()) {
count = chars.get(c);
count = Integer.valueOf(count != null ? count + 1 : 1);
chars.put(c, count);
}
for (char c : s1.toCharArray()) {
count = chars.get(c);
if (count == null) {
return false;
} else {
count--;
chars.put(c, count);
}
}
for (Integer i : chars.values()) {
if (i != 0) {
return false;
}
}
return true;
} else {
return false;
}
}

Esta función se está ejecutando realmente en O (N) ... en lugar de O (NlogN) para la solución que ordena las cadenas. Si tuviera que asumir que vas a utilizar solo caracteres alfabéticos, solo podría usar una matriz de 26 ints (de la a a la z sin acentos ni decoraciones) en lugar del hashmap.

Si definimos eso: N = | one | + | dos | hacemos una iteración sobre N (una vez más uno para incrementar los contadores, y una vez para disminuirlos sobre dos). Luego, para verificar los totales, repetimos en mose N / 2.

Los otros algoritmos descritos tienen una ventaja: no usan memoria adicional, suponiendo que Arrays.sort utiliza versiones in situ de QuickSort o merge sort. Pero dado que estamos hablando de anagramas, asumiré que estamos hablando de lenguajes humanos, por lo tanto las palabras no deberían ser lo suficientemente largas como para dar problemas de memoria.

Answer 3

Alguna otra solución sin ordenar.

public static boolean isAnagram(String s1, String s2){
//case insensitive anagram
StringBuffer sb = new StringBuffer(s2.toLowerCase());
for (char c: s1.toLowerCase().toCharArray()){
if (Character.isLetter(c)){
int index = sb.indexOf(String.valueOf(c));
if (index == -1){
//char does not exist in other s2
return false;
}
sb.deleteCharAt(index);
}
}
for (char c: sb.toString().toCharArray()){
//only allow whitespace as left overs
if (!Character.isWhitespace(c)){
return false;
}
}
return true;
}

Answer 4

Aquí está mi solución. Primero explotad las cuerdas en matrices de caracteres, luego clasifícalas y luego compara si son iguales o no. Supongo que la complejidad del tiempo de este código es O (a + b). Si a = b podemos decir O (2A)

public boolean isAnagram(String s1, String s2) {
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
if (s1.length() != s2.length())
return false;
char arr1[] = s1.toCharArray();
char arr2[] = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
for (char c : arr1) {
sb1.append(c);
}
for (char c : arr2) {
sb2.append(c);
}
System.out.println(sb1.toString());
System.out.println(sb2.toString());
if (sb1.toString().equals(sb2.toString()))
return true;
else
return false;
}

Answer 5

Aquí hay una solución rápida y sencilla de O (n) sin usar clasificación o múltiples bucles o mapas hash. Incrementamos el recuento de cada carácter en la primera matriz y disminuimos el recuento de cada carácter en la segunda matriz. Si la matriz de recuentos resultante está llena de ceros, las cadenas son anagramas. Se puede ampliar para incluir otros caracteres aumentando el tamaño de la matriz de conteos.

class AnagramsFaster{
private static boolean compare(String a, String b){
char[] aArr = a.toLowerCase().toCharArray(), bArr = b.toLowerCase().toCharArray();
if (aArr.length != bArr.length)
return false;
int[] counts = new int[26]; // An array to hold the number of occurrences of each character
for (int i = 0; i < aArr.length; i++){
counts[aArr[i]-97]++; // Increment the count of the character at i
counts[bArr[i]-97]--; // Decrement the count of the character at i
}
// If the strings are anagrams, the counts array will be full of zeros
for (int i = 0; i<26; i++)
if (counts[i] != 0)
return false;
return true;
}
public static void main(String[] args){
System.out.println(compare(args[0], args[1]));
}
}

Answer 6

Cómo un matemático podría pensar sobre el problema antes de escribir cualquier código :

1. La relación "son anagramas" entre cadenas es una relación de equivalencia , por lo que divide el conjunto de todas las cadenas en clases de equivalencia.
2. Supongamos que tenemos una regla para elegir un representante (cuna) de cada clase, luego es fácil probar si dos clases son iguales al comparar a sus representantes.
3. Un representante obvio para un conjunto de cadenas es "el elemento más pequeño por orden lexicográfico ", que es fácil de calcular a partir de cualquier elemento mediante la clasificación. Por ejemplo, el representante de la clase de anagrama que contiene ''sombrero'' es ''aht''.

En su ejemplo, "maestro de escuela" y "clase" son anagramas porque ambos están en la clase de anagrama con cuna "acehlmoorsst".

En pseudocódigo:

>>> def crib(word):
... return sorted(word)
...
>>> crib("schoolmaster") == crib("theclassroom")
True

Answer 7

Dos palabras son anagramas entre sí si contienen el mismo número de caracteres y los mismos caracteres. Solo debe ordenar los caracteres en orden lexicográfico y comparar si String a es igual a String b en todos los pasos.

Aquí hay un ejemplo de código. Busca Arrays en la API para entender lo que está sucediendo aquí.

public boolean isAnagram(String firstWord, String secondWord) {
char[] word1 = firstWord.replaceAll("[//s]", "").toCharArray();
char[] word2 = secondWord.replaceAll("[//s]", "").toCharArray();
Arrays.sort(word1);
Arrays.sort(word2);
return Arrays.equals(word1, word2);
}

Answer 8

El algoritmo más rápido sería asignar cada uno de los 26 caracteres en inglés a un número primo único. Luego calcule el producto de la cadena. Según el teorema fundamental de la aritmética, 2 cadenas son anagramas si y solo si sus productos son los mismos.

Answer 9

El enfoque de clasificación no es el mejor. Toma O (n) espacio y O (nlogn) tiempo. En su lugar, cree un mapa hash de caracteres y cuéntelos (incremente los caracteres que aparecen en la primera cadena y disminuya los caracteres que aparecen en la segunda cadena). Cuando algún conteo llega a cero, elimínelo del hash. Finalmente, si dos cadenas son anagramas, entonces la tabla hash estará vacía al final; de lo contrario, no estará vacía.

Un par de notas importantes: (1) Ignorar letra mayúscula y (2) Ignorar espacio en blanco.

Aquí está el análisis detallado y la implementación en C #: Prueba si dos cadenas son Anagramas

Answer 10

En mi humilde opinión, la solución más eficiente fue provista por @Siguza, la he extendido para cubrir cadenas con espacio, por ejemplo: "William Shakespeare", "Soy un deletreo débil", "Maestro de escuela", "El aula"

public int getAnagramScore(String word, String anagram) {
if (word == null || anagram == null) {
throw new NullPointerException("Both, word and anagram, must be non-null");
}
char[] wordArray = word.trim().toLowerCase().toCharArray();
char[] anagramArray = anagram.trim().toLowerCase().toCharArray();
int[] alphabetCountArray = new int[26];
int reference = ''a'';
for (int i = 0; i < wordArray.length; i++) {
if (!Character.isWhitespace(wordArray[i])) {
alphabetCountArray[wordArray[i] - reference]++;
}
}
for (int i = 0; i < anagramArray.length; i++) {
if (!Character.isWhitespace(anagramArray[i])) {
alphabetCountArray[anagramArray[i] - reference]--;
}
}
for (int i = 0; i < 26; i++)
if (alphabetCountArray[i] != 0)
return 0;
return word.length();
}

Answer 11

Estamos caminando dos cadenas de igual longitud y rastreando las diferencias entre ellas. No nos importan las diferencias, solo queremos saber si tienen los mismos personajes o no. Podemos hacer esto en O (n / 2) sin ningún procesamiento posterior (o muchos primos).

public class TestAnagram {
public static boolean isAnagram(String first, String second) {
String positive = first.toLowerCase();
String negative = second.toLowerCase();
if (positive.length() != negative.length()) {
return false;
}
int[] counts = new int[26];
int diff = 0;
for (int i = 0; i < positive.length(); i++) {
int pos = (int) positive.charAt(i) - 97; // convert the char into an array index
if (counts[pos] >= 0) { // the other string doesn''t have this
diff++; // an increase in differences
} else { // it does have it
diff--; // a decrease in differences
}
counts[pos]++; // track it
int neg = (int) negative.charAt(i) - 97;
if (counts[neg] <= 0) { // the other string doesn''t have this
diff++; // an increase in differences
} else { // it does have it
diff--; // a decrease in differences
}
counts[neg]--; // track it
}
return diff == 0;
}
public static void main(String[] args) {
System.out.println(isAnagram("zMarry", "zArmry")); // true
System.out.println(isAnagram("basiparachromatin", "marsipobranchiata")); // true
System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterone")); // true
System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterons")); // false
System.out.println(isAnagram("zArmcy", "zArmry")); // false
}
}

Sí, este código depende del juego de caracteres en inglés ASCII de minúsculas, pero no debería ser difícil modificarlo a otros idiomas. Siempre puede usar un Mapa [Carácter, Int.] Para rastrear la misma información, será más lento.

Answer 12

Gracias por señalar para hacer un comentario, al hacer comentarios encontré que había una lógica incorrecta. Corregí la lógica y añadí un comentario para cada fragmento de código.

// Time complexity: O(N) where N is number of character in String
// Required space :constant space.
// will work for string that contains ASCII chars
private static boolean isAnagram(String s1, String s2) {
// if length of both string''s are not equal then they are not anagram of each other
if(s1.length() != s2.length())return false;
// array to store the presence of a character with number of occurrences.
int []seen = new int[256];
// initialize the array with zero. Do not need to initialize specifically since by default element will initialized by 0.
// Added this is just increase the readability of the code.
Arrays.fill(seen, 0);
// convert each string to lower case if you want to make ABC and aBC as anagram, other wise no need to change the case.
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
// iterate through the first string and count the occurrences of each character
for(int i =0; i < s1.length(); i++){
seen[s1.charAt(i)] = seen[s1.charAt(i)] +1;
}
// iterate through second string and if any char has 0 occurrence then return false, it mean some char in s2 is there that is not present in s1.
// other wise reduce the occurrences by one every time .
for(int i =0; i < s2.length(); i++){
if(seen[s2.charAt(i)] ==0)return false;
seen[s2.charAt(i)] = seen[s2.charAt(i)]-1;
}
// now if both string have same occurrence of each character then the seen array must contains all element as zero. if any one has non zero element return false mean there are
// some character that either does not appear in one of the string or/and mismatch in occurrences
for(int i = 0; i < 256; i++){
if(seen[i] != 0)return false;
}
return true;
}

Answer 13

Lo sentimos, la solución está en C #, pero creo que los diferentes elementos utilizados para llegar a la solución son bastante intuitivos. Se requiere un ligero ajuste para las palabras con guiones, pero para las palabras normales debería funcionar bien.

 internal bool isAnagram(string input1,string input2)
{
Dictionary<char, int> outChars = AddToDict(input2.ToLower().Replace(" ", ""));
input1 = input1.ToLower().Replace(" ","");
foreach(char c in input1)
{
if (outChars.ContainsKey(c))
{
if (outChars[c] > 1)
outChars[c] -= 1;
else
outChars.Remove(c);
}
}
return outChars.Count == 0;
}
private Dictionary<char, int> AddToDict(string input)
{
Dictionary<char, int> inputChars = new Dictionary<char, int>();
foreach(char c in input)
{
if(inputChars.ContainsKey(c))
{
inputChars[c] += 1;
}
else
{
inputChars.Add(c, 1);
}
}
return inputChars;
}

Answer 14

Mucha gente ha presentado soluciones, pero solo quiero hablar sobre la complejidad algorítmica de algunos de los enfoques comunes:

• El simple "ordenar los caracteres usando el Arrays.sort() " va a ser O(N log N) .

• Si usa la clasificación de radix, eso se reduce a O(N) con O(M) espacio, donde M es el número de caracteres distintos en el alfabeto. (Eso es 26 en inglés ... pero en teoría deberíamos considerar anagramas multilingües).

• El "contar los caracteres" usando una matriz de conteos también es O(N) ... y más rápido que ordenar por radix porque no necesita reconstruir la cadena ordenada. El uso del espacio será O(M) .

• A "contar los caracteres" usando un diccionario, hashmap, treemap o equivalente será más lento que el enfoque de la matriz, a menos que el alfabeto sea enorme.

• El enfoque elegante del "producto de primos" es desafortunadamente O(N^2) en el peor de los casos. Esto se debe a que por palabras o frases suficientemente largas, el producto de los números primos no cabe en un long . Eso significa que necesitaría usar BigInteger , y N multiplicando un BigInteger por una pequeña constante es O(N^2) .

  Para un alfabeto grande hipotético, el factor de escala va a ser grande. El peor uso de espacio para contener el producto de los números primos como BigInteger es (creo) O(N*logM) .

• Un enfoque basado en hashcode es generalmente O(N) si las palabras no son anagramas. Si los códigos hash son iguales, entonces aún necesita hacer una prueba de anagrama adecuada. Entonces esta no es una solución completa.

Answer 15

Muchas respuestas complicadas aquí. Basándonos en la respuesta aceptada y el comentario que menciona la cuestión ''ac'' - ''bb'' suponiendo que A = 1 B = 2 C = 3, podríamos simplemente usar el cuadrado de cada entero que represente un carácter y resolver el problema:

public boolean anagram(String s, String t) {
if(s.length() != t.length())
return false;
int value = 0;
for(int i = 0; i < s.length(); i++){
value += ((int)s.charAt(i))^2;
value -= ((int)t.charAt(i))^2;
}
return value == 0;
}

Answer 16

O (n) solución sin ningún tipo de clasificación y usando solo un mapa.

public boolean isAnagram(String leftString, String rightString) {
if (leftString == null || rightString == null) {
return false;
} else if (leftString.length() != rightString.length()) {
return false;
}
Map<Character, Integer> 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. Tienes que colocar tu alfabeto aquí:

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<Character, Integer> 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;
}

Answer 17

Si ordena cualquiera de las matrices, la solución se convierte en O (n log n). pero si usas un hashmap, es O (n). probado y trabajando.

char[] word1 = "test".toCharArray();
char[] word2 = "tes".toCharArray();
Map<Character, Integer> lettersInWord1 = new HashMap<Character, Integer>();
for (char c : word1) {
int count = 1;
if (lettersInWord1.containsKey(c)) {
count = lettersInWord1.get(c) + 1;
}
lettersInWord1.put(c, count);
}
for (char c : word2) {
int count = -1;
if (lettersInWord1.containsKey(c)) {
count = lettersInWord1.get(c) - 1;
}
lettersInWord1.put(c, count);
}
for (char c : lettersInWord1.keySet()) {
if (lettersInWord1.get(c) != 0) {
return false;
}
}
return true;

Answer 18

Soy desarrollador de C ++ y el siguiente código está en C ++. Creo que la forma más rápida y fácil de hacerlo sería la siguiente:

Cree un vector de enteros de tamaño 26, con todas las ranuras inicializadas a 0, y coloque cada carácter de la cadena en la posición apropiada en el vector. Recuerde, el vector está en orden alfabético, por lo que si la primera letra de la cadena es z, iría en myvector [26]. Nota: Esto se puede hacer usando caracteres ASCII, así que, esencialmente, su código se verá más o menos así:

string s = zadg;
for(int i =0; i < s.size(); ++i){
myvector[s[i] - ''a''] = myvector[''s[i] - ''a''] + 1;
}

Entonces, insertar todos los elementos tomaría O (n) tiempo ya que solo atravesaría la lista una vez. Ahora puede hacer exactamente lo mismo para la segunda cadena y eso también le tomaría a O (n) tiempo. Luego puede comparar los dos vectores al verificar si los contadores en cada ranura son iguales. Si lo son, eso significa que tienes el mismo número de CADA caracter en ambas cadenas y por lo tanto son anagramas. La comparación de los dos vectores también debería tomar el tiempo O (n) ya que solo atraviesa una vez.

Nota: El código solo funciona para una sola palabra de caracteres. Si tiene espacios, números y símbolos, puede crear un vector de tamaño 96 (caracteres ASCII 32-127) y en lugar de decir ''a'' usted diría '''' como el carácter de espacio es el primero en el Lista ASCII de personajes.

Espero que eso ayude. Si cometí un error en alguna parte, por favor deje un comentario.

Answer 19

Un método simple para determinar si testString es un anagrama de baseString.

private static boolean isAnagram(String baseString, String testString){
//Assume that there are no empty spaces in either string.
if(baseString.length() != testString.length()){
System.out.println("The 2 given words cannot be anagram since their lengths are different");
return false;
}
else{
if(baseString.length() == testString.length()){
if(baseString.equalsIgnoreCase(testString)){
System.out.println("The 2 given words are anagram since they are identical.");
return true;
}
else{
List<Character> list = new ArrayList<>();
for(Character ch : baseString.toLowerCase().toCharArray()){
list.add(ch);
}
System.out.println("List is : "+ list);
for(Character ch : testString.toLowerCase().toCharArray()){
if(list.contains(ch)){
list.remove(ch);
}
}
if(list.isEmpty()){
System.out.println("The 2 words are anagrams");
return true;
}
}
}
}
return false;
}

Answer 20

Una respuesta similar puede haber sido publicada en C ++, aquí está de nuevo en Java. Tenga en cuenta que la forma más elegante sería utilizar un Trie para almacenar los caracteres en orden, sin embargo, esa es una solución más compleja. Una forma es usar un hashset para almacenar todas las palabras que estamos comparando y luego compararlas una a una. Para compararlos, cree una matriz de caracteres con el índice que represente el valor ANCII de los caracteres (utilizando un normalizador ya que, por ejemplo, el valor ANCII de ''a'' es 97) y el valor que representa el recuento de ocurrencias de ese carácter. Esto se ejecutará en el tiempo O (n) y usará el espacio O (m * z) donde m es el tamaño de la palabra actual yz el tamaño de la palabra almacenada, para los cuales creamos un Char [].

public static boolean makeAnagram(String currentWord, String storedWord){
if(currentWord.length() != storedWord.length()) return false;//words must be same length
Integer[] currentWordChars = new Integer[totalAlphabets];
Integer[] storedWordChars = new Integer[totalAlphabets];
//create a temp Arrays to compare the words
storeWordCharacterInArray(currentWordChars, currentWord);
storeWordCharacterInArray(storedWordChars, storedWord);
for(int i = 0; i < totalAlphabets; i++){
//compare the new word to the current charList to see if anagram is possible
if(currentWordChars[i] != storedWordChars[i]) return false;
}
return true;//and store this word in the HashSet of word in the Heap
}
//for each word store its characters
public static void storeWordCharacterInArray(Integer[] characterList, String word){
char[] charCheck = word.toCharArray();
for(char c: charCheck){
Character cc = c;
int index = cc.charValue()-indexNormalizer;
characterList[index] += 1;
}
}

Answer 21

A way to solve this - based on Sai Kiran''s answer..

import java.util.Scanner;
public class Anagram {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter first word : ");
String word1 = sc.nextLine();
System.out.print("Enter second word : ");
String word2 = sc.nextLine();
sc.close();
System.out.println("Is Anagram : " + isAnagram(word1, word2));
}
private static boolean isAnagram(String word1, String word2) {
if (word1.length() != word2.length()) {
System.err.println("Words length didn''t match!");
return false;
}
char ch1, ch2;
int len = word1.length(), sumOfWord1Chars = 0, sumOfWord2Chars = 0;
for (int i = 0; i < len; i++) {
ch1 = word1.charAt(i);
if (word2.indexOf(ch1) < 0) {
System.err.println("''" + ch1 + "'' not found in /"" + word2
+ "/"");
return false;
}
sumOfWord1Chars += word1.charAt(i);
ch2 = word2.charAt(i);
if (word1.indexOf(ch2) < 0) {
System.err.println("''" + ch2 + "'' not found in /"" + word1
+ "/"");
return false;
}
sumOfWord2Chars += word2.charAt(i);
}
if (sumOfWord1Chars != sumOfWord2Chars) {
System.err
.println("Sum of both words didn''t match, i.e., words having same characters but with different counts!");
return false;
}
return true;
}
}

Answer 22

Here is another approach using HashMap in Java

public static boolean isAnagram(String first, String second) {
if (first == null || second == null) {
return false;
}
if (first.length() != second.length()) {
return false;
}
return doCheckAnagramUsingHashMap(first.toLowerCase(), second.toLowerCase());
}
private static boolean doCheckAnagramUsingHashMap(final String first, final String second) {
Map<Character, Integer> counter = populateMap(first, second);
return validateMap(counter);
}
private static boolean validateMap(Map<Character, Integer> counter) {
for (int val : counter.values()) {
if (val != 0) {
return false;
}
}
return true;
}

Here is the test case

@Test
public void anagramTest() {
assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
assertFalse(StringUtil.isAnagram("Hello", "hell"));
assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));
}

Answer 23

I had written this program in java. I think this might also help:

public class Anagram {
public static void main(String[] args) {
checkAnagram("listen", "silent");
}
public static void checkAnagram(String str1, String str2) {
boolean isAnagram = false;
str1 = sortStr(str1);
str2 = sortStr(str2);
if (str1.equals(str2)) {
isAnagram = true;
}
if (isAnagram) {
System.out.println("Two strings are anagram");
} else {
System.out.println("Two string are not anagram");
}
}
public static String sortStr(String str) {
char[] strArr = str.toCharArray();
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j < str.length(); j++) {
if (strArr[i] > strArr[j]) {
char temp = strArr[i];
strArr[i] = strArr[j];
strArr[j] = temp;
}
}
}
String output = String.valueOf(strArr);
return output;
}
}

Answer 24

I know this is an old question. However, I''m hoping this can be of help to someone. The time complexity of this solution is O(n^2).

public boolean areAnagrams(final String word1, final String word2) {
if (word1.length() != word2.length())
return false;
if (word1.equals(word2))
return true;
if (word1.length() == 0 && word2.length() == 0)
return true;
String secondWord = word2;
for (int i = 0; i < word1.length(); i++) {
if (secondWord.indexOf(word1.charAt(i)) == -1)
return false;
secondWord = secondWord.replaceFirst(word1.charAt(i) + "", "");
}
if (secondWord.length() > 0)
return false;
return true;
}

Answer 25

I saw that no one has used the "hashcode" approach to find out the anagrams. I found my approach little different than the approaches discussed above hence thought of sharing it. I wrote the below code to find the anagrams which works in O(n).

/**
* This class performs the logic of finding anagrams
* @author ripudam
*
*/
public class AnagramTest {
public static boolean isAnagram(final String word1, final String word2) {
if (word1 == null || word2 == null || word1.length() != word2.length()) {
return false;
}
if (word1.equals(word2)) {
return true;
}
final AnagramWrapper word1Obj = new AnagramWrapper(word1);
final AnagramWrapper word2Obj = new AnagramWrapper(word2);
if (word1Obj.equals(word2Obj)) {
return true;
}
return false;
}
/*
* Inner class to wrap the string received for anagram check to find the
* hash
*/
static class AnagramWrapper {
String word;
public AnagramWrapper(final String word) {
this.word = word;
}
@Override
public boolean equals(final Object obj) {
return hashCode() == obj.hashCode();
}
@Override
public int hashCode() {
final char[] array = word.toCharArray();
int hashcode = 0;
for (final char c : array) {
hashcode = hashcode + (c * c);
}
return hashcode;
}
}
}

Answer 26

So far all proposed solutions work with separate char items, not code points. I''d like to propose two solutions to properly handle surrogate pairs as well (those are characters from U+10000 to U+10FFFF , composed of two char items).

1) One-line O(n logn) solution which utilizes Java 8 CharSequence.codePoints() stream:

static boolean areAnagrams(CharSequence a, CharSequence b) {
return Arrays.equals(a.codePoints().sorted().toArray(),
b.codePoints().sorted().toArray());
}

2) Less elegant O(n) solution (in fact, it will be faster only for long strings with low chances to be anagrams) :

static boolean areAnagrams(CharSequence a, CharSequence b) {
int len = a.length();
if (len != b.length())
return false;
// collect codepoint occurrences in "a"
Map<Integer, Integer> ocr = new HashMap<>(64);
a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum));
// for each codepoint in "b", look for matching occurrence
for (int i = 0, c = 0; i < len; i += Character.charCount(c)) {
int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0);
if (cc == 0)
return false;
ocr.put(c, cc - 1);
}
return true;
}

Answer 27

You should use something like that:

 for (int i...) {
isFound = false;
for (int j...) {
if (...) {
...
isFound = true;
}
}

Default value for isFound should be false. Just it

Answer 28

 /*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Algorithms;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import javax.swing.JOptionPane;
/**
*
* @author Mokhtar
*/
public class Anagrams {
//Write aprogram to check if two words are anagrams
public static void main(String[] args) {
Anagrams an=new Anagrams();
ArrayList<String> l=new ArrayList<String>();
String result=JOptionPane.showInputDialog("How many words to test anagrams");
if(Integer.parseInt(result) >1)
{
for(int i=0;i<Integer.parseInt(result);i++)
{
String word=JOptionPane.showInputDialog("Enter word #"+i);
l.add(word);
}
System.out.println(an.isanagrams(l));
}
else
{
JOptionPane.showMessageDialog(null, "Can not be tested, /nYou can test two words or more");
}
}
private static String sortString( String w )
{
char[] ch = w.toCharArray();
Arrays.sort(ch);
return new String(ch);
}
public boolean isanagrams(ArrayList<String> l)
{
boolean isanagrams=true;
ArrayList<String> anagrams = null;
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for(int i=0;i<l.size();i++)
{
String word = l.get(i);
String sortedWord = sortString(word);
anagrams = map.get( sortedWord );
if( anagrams == null ) anagrams = new ArrayList<String>();
anagrams.add(word);
map.put(sortedWord, anagrams);
}
for(int h=0;h<l.size();h++)
{
if(!anagrams.contains(l.get(h)))
{
isanagrams=false;
break;
}
}
return isanagrams;
//}
}
}

Answer 29

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/**
* Check if Anagram by Prime Number Logic
* @author Pallav
*
*/
public class Anagram {
public static void main(String args[]) {
System.out.println(isAnagram(args[0].toUpperCase(),
args[1].toUpperCase()));
}
/**
*
* @param word : The String 1
* @param anagram_word : The String 2 with which Anagram to be verified
* @return true or false based on Anagram
*/
public static Boolean isAnagram(String word, String anagram_word) {
//If length is different return false
if (word.length() != anagram_word.length()) {
return false;
}
char[] words_char = word.toCharArray();//Get the Char Array of First String
char[] anagram_word_char = anagram_word.toCharArray();//Get the Char Array of Second String
int words_char_num = 1;//Initialize Multiplication Factor to 1
int anagram_word_num = 1;//Initialize Multiplication Factor to 1 for String 2
Map<Character, Integer> wordPrimeMap = wordPrimeMap();//Get the Prime numbers Mapped to each alphabets in English
for (int i = 0; i < words_char.length; i++) {
words_char_num *= wordPrimeMap.get(words_char[i]);//get Multiplication value for String 1
}
for (int i = 0; i < anagram_word_char.length; i++) {
anagram_word_num *= wordPrimeMap.get(anagram_word_char[i]);//get Multiplication value for String 2
}
return anagram_word_num == words_char_num;
}
/**
* Get the Prime numbers Mapped to each alphabets in English
* @return
*/
public static Map<Character, Integer> wordPrimeMap() {
List<Integer> primes = primes(26);
int k = 65;
Map<Character, Integer> map = new TreeMap<Character, Integer>();
for (int i = 0; i < primes.size(); i++) {
Character character = (char) k;
map.put(character, primes.get(i));
k++;
}
// System.out.println(map);
return map;
}
/**
* get first N prime Numbers where Number is greater than 2
* @param N : Number of Prime Numbers
* @return
*/
public static List<Integer> primes(Integer N) {
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);
int n = 5;
int k = 0;
do {
boolean is_prime = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
is_prime = false;
break;
}
}
if (is_prime == true) {
primes.add(n);
}
n++;
// System.out.println(k);
} while (primes.size() < N);
// }
return primes;
}
}

Answer 30

private static boolean checkAnagram(String s1, String s2) {
if (s1 == null || s2 == null) {
return false;
} else if (s1.length() != s2.length()) {
return false;
}
char[] a1 = s1.toCharArray();
char[] a2 = s2.toCharArray();
int length = s2.length();
int s1Count = 0;
int s2Count = 0;
for (int i = 0; i < length; i++) {
s1Count+=a1[i];
s2Count+=a2[i];
}
return s2Count == s1Count ? true : false;
}