ti-enxame.com

Como encontrar as duas palavras são anagramas

Eu tenho um programa que mostra se duas palavras são anagramas umas das outras. Existem alguns exemplos que não funcionam corretamente e eu gostaria de receber ajuda, embora se não fosse avançado, seria ótimo, já que eu sou um programador do primeiro ano. "professor" e "sala de aula" são anagramas uns dos outros, no entanto, quando eu mudo "a sala de aula" para "o banheiro", ele ainda diz que eles são anagramas, o que estou fazendo errado?

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;
  }
}
42
Chilli

O algoritmo mais rápido seria mapear cada um dos 26 caracteres ingleses para um número primo único. Em seguida, calcule o produto da string. Pelo teorema fundamental da aritmética, 2 cordas são anagramas se e somente se seus produtos são os mesmos.

90
SeriousBusiness

Duas palavras são anagramas uma da outra se contiverem o mesmo número de caracteres e os mesmos caracteres. Você só precisa classificar os caracteres em ordem lexicográfica e determinar se todos os caracteres em uma sequência são iguais a e na mesma ordem que todos os caracteres na outra sequência.

Aqui está um exemplo de código. Olhe para Arrays na API para entender o que está acontecendo aqui.

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);
}
100
Makoto

Se você classificar qualquer array, a solução se tornará O (n log n). mas se você usar um hashmap, será O (n). testado e funcionando.

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;
48
jb.

Aqui está uma solução simples e rápida O(n) sem usar classificação ou vários loops ou mapas de hash. Nós incrementamos a contagem de cada caractere na primeira matriz e diminuímos a contagem de cada caractere na segunda matriz. Se a matriz de contagens resultante estiver cheia de zeros, as sequências serão anagramas. Pode ser expandido para incluir outros caracteres aumentando o tamanho da matriz de contagens.

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]));
    }
}
25
Aswin

Muitas pessoas apresentaram soluções, mas eu só quero falar sobre a complexidade algorítmica de algumas das abordagens comuns:

  • A abordagem simples "classificar os caracteres usando Arrays.sort()" será O(N log N).

  • Se você usar ordenação por radix, isso reduz para O(N) com O(M) space, onde M é o número de caracteres distintos no alfabeto. (Isso é 26 em inglês ... mas, em teoria, devemos considerar anagramas multilíngues.)

  • A "contagem dos caracteres" usando uma matriz de contagens também é O(N) ... e mais rápida que radix sort porque você não precisa reconstruir a string ordenada. O uso do espaço será O(M).

  • Uma "contagem dos caracteres" usando um dicionário, hashmap, treemap ou equivalente será mais lenta que a matriz, a menos que o alfabeto seja enorme.

  • A abordagem "produto-de-primos" é, infelizmente, O(N^2) no pior dos casos Isso ocorre porque, para palavras ou frases longas o suficiente, o produto dos primos não se ajusta a um long. Isso significa que você precisaria usar BigInteger e N multiplicando um BigInteger por uma pequena constante é O(N^2)

    Para um alfabeto grande hipotético, o fator de escala será grande. O pior uso de espaço para armazenar o produto dos primos como um BigInteger é (eu acho) O(N*logM).

  • Uma abordagem baseada em hashcode geralmente é O(N) se as palavras não forem anagramas. Se os hashcodes são iguais, então você ainda precisa fazer um teste de anagrama apropriado. Então esta não é uma solução completa.

22
Stephen C

O (n) solução sem qualquer tipo de classificação e usando apenas um 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;
}

e menos solução genérica, mas um pouco mais rápida. Você tem que colocar seu alfabeto aqui:

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;
}
6
goroncy

Estamos caminhando duas cordas de igual comprimento e rastreando as diferenças entre elas. Nós não nos importamos com as diferenças, só queremos saber se eles têm os mesmos caracteres ou não. Nós podemos fazer isso em O(n/2) sem qualquer pós-processamento (ou muitos 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
  }
}

Sim, este código é dependente do conjunto de caracteres ingleses ASCII de caracteres minúsculos, mas não deve ser difícil de modificar para outros idiomas. Você sempre pode usar um Map [Character, Int] para rastrear a mesma informação, será apenas mais lento.

4
Jeff Thomas

Muitas respostas complicadas aqui. Base na resposta aceito e o comentário mencionando a questão 'ac' - 'bb' assumindo A = 1 B = 2 C = 3, poderíamos simplesmente usar o quadrado de cada inteiro que representa um caractere e resolva o 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;
}
3
chakming
    /*
 * 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;
        //}
        }

}
3
Mokhtar Kalmoush

Usando mais memória (um HashMap de no máximo N/2 elementos) não precisamos ordenar as strings.

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;
    }
}

Essa função está sendo executada em O(N) ... em vez de O(NlogN) para a solução que classifica as cadeias. Se eu supusesse que você usaria apenas caracteres alfabéticos, eu só poderia usar uma matriz de 26 ints (de a até z sem acentos ou decorações) em vez do hashmap.

Se definirmos isso: N = | um | + | two | fazemos uma iteração sobre N (uma vez sobre uma para incrementar os contadores e uma para decrementar sobre duas). Então, para verificar os totais, nós iteramos na mose N/2.

Os outros algoritmos descritos têm uma vantagem: eles não usam memória extra supondo que o Arrays.sort use versões locais do QuickSort ou do merge sort. Mas como estamos falando de anagramas, vou assumir que estamos falando de linguagens humanas, portanto, as palavras não devem ser longas o suficiente para dar problemas de memória.

3
ɭɘ ɖɵʊɒɼɖ 江戸

Eu sou um desenvolvedor C++ e o código abaixo está em C++. Eu acredito que a maneira mais rápida e fácil de fazê-lo seria o seguinte:

Crie um vetor de ints de tamanho 26, com todos os slots inicializados como 0, e coloque cada caractere da string na posição apropriada no vetor. Lembre-se, o vetor está em ordem alfabética e, portanto, se a primeira letra da string for z, ela entrará no myvector [26]. Nota: Isso pode ser feito usando caracteres ASCII, então, essencialmente, seu código será parecido com isto:

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

Assim, inserir todos os elementos levaria a hora O(n), já que você percorreria a lista apenas uma vez. Agora você pode fazer exatamente a mesma coisa para a segunda string e isso também levaria O(n) tempo. Você pode comparar os dois vetores verificando se os contadores em cada slot são iguais. Se eles são, isso significa que você teve o mesmo número de cada caractere em ambas as cordas e, portanto, eles são anagramas. A comparação dos dois vetores também deve levar O(n) tempo como você está percorrendo apenas uma vez. 

Nota: O código só funciona para uma única palavra de caracteres. Se você tem espaços, números e símbolos, você pode simplesmente criar um vetor de tamanho 96 (caracteres ASCII 32-127) e ao invés de dizer - 'a' você diria - '' já que o caractere de espaço é o primeiro no ASCII lista de caracteres.

Espero que isso ajude. Se eu cometi um erro em algum lugar, por favor deixe um comentário.

3
muneebahmad

Obrigado por apontar para fazer comentários, ao fazer comentários, descobri que havia uma lógica incorreta. Eu corrigi a lógica e adicionei comentários para cada pedaço 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;
}
2
Kuldeep Singh

Até agora, todas as soluções propostas funcionam com itens char separados, não com pontos de código. Eu gostaria de propor duas soluções para manipular corretamente substituir pares bem (esses são caracteres de U + 10000 para U + 10FFFF , composto de dois itens char).

1) Solução de uma linha O (n logn) que utiliza Java 8 CharSequence.codePoints() stream:

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

2) Menos elegante O(n) solution (na verdade, será mais rápido apenas para strings longas com poucas chances de serem anagramas):

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;
}
1
Alex Salauyou
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;
    }

}
1
Kumar Pallav

IMHO, a solução mais eficiente foi fornecida pelo @Siguza, eu estendi-a para cobrir seqüências com espaço, por exemplo, "William Shakespeare", "Eu sou um soletrador fraco", "Mestre da escola", "A sala de 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();

    }
1
Kaliyug Antagonist

Aqui está a minha solução. Primeiro explodir as seqüências de caracteres em matrizes de caracteres, em seguida, classificá-los e, em seguida, comparando se eles são iguais ou não. Eu acho que a complexidade do tempo deste código é O (a + b). Se a = b, podemos dizer 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;

    }
1
Türkmen Mustafa Demirci

Uma resposta semelhante pode ter sido postada em C++, aqui está novamente em Java. Observe que a maneira mais elegante seria usar um Trie para armazenar os caracteres em ordem de classificação, no entanto, essa é uma solução mais complexa. Uma maneira é usar um hashset para armazenar todas as palavras que estamos comparando e depois compará-las uma a uma. Para compará-los, crie uma matriz de caracteres com o índice representando o valor ANCII dos caracteres (usando um normalizador, ou seja, o valor ANCII de 'a' é 97) e o valor representando a contagem de ocorrências desse caractere. Isto irá rodar em O(n) tempo e usar O (m * z) espaço onde m é o tamanho do currentWord ez o tamanho do storedWord, ambos para os quais criamos um 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;
    }
}
1
ak_2050

A abordagem de classificação não é a melhor. Ele toma o espaço O(n) e o tempo O(nlogn). Em vez disso, crie um mapa hash de caracteres e conte-os (incremente os caracteres que aparecem na primeira cadeia e diminua os caracteres que aparecem na segunda cadeia). Quando alguma contagem chegar a zero, remova-a do hash. Finalmente, se duas strings forem anagramas, a tabela de hash estará vazia no final - caso contrário, não estará vazia.

Algumas notas importantes: (1) Ignore o caso de letras e (2) Ignore o espaço em branco.

Aqui está a análise detalhada e implementação em C #: Teste se duas seqüências são anagramas

0
Zoran Horvat

Aqui está outra abordagem usando o HashMap em 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;
}

Aqui está o caso de teste

@Test
public void anagramTest() {
    assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
    assertFalse(StringUtil.isAnagram("Hello", "hell"));
    assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));       
}
0
craftsmannadeem
// When this method returns 0 means strings are Anagram, else Not.

public static int isAnagram(String str1, String str2) {
        int value = 0;
        if (str1.length() == str2.length()) {
            for (int i = 0; i < str1.length(); i++) {
                value = value + str1.charAt(i);
                value = value - str2.charAt(i);
            }

        } else {
            value = -1;
        }
        return value;
    }
0
shiv

A solução mais simples com complexidade O(N) está usando o Mapa.

public static Boolean checkAnagram(String string1, String string2) {
    Boolean anagram = true;

    Map<Character, Integer> map1 = new HashMap<>();
    Map<Character, Integer> map2 = new HashMap<>();


    char[] chars1 = string1.toCharArray();
    char[] chars2 = string2.toCharArray();

    for(int i=0; i<chars1.length; i++) {
        if(map1.get(chars1[i]) == null) {
            map1.put(chars1[i], 1);
        } else {
            map1.put(chars1[i], map1.get(chars1[i])+1);
        }

        if(map2.get(chars2[i]) == null) {
            map2.put(chars2[i], 1);
        } else {
            map2.put(chars2[i], map2.get(chars2[i])+1);
        }
    }

    Set<Map.Entry<Character, Integer>> entrySet1 = map1.entrySet();
    Set<Map.Entry<Character, Integer>> entrySet2 = map2.entrySet();
    for(Map.Entry<Character, Integer> entry:entrySet1) {

        if(entry.getValue() != map2.get(entry.getKey())) {
            anagram = false;
            break;
        }
    }

    return anagram;
}
0
chaatna

Vi que ninguém usou a abordagem "hashcode" para descobrir os anagramas. Eu achei minha abordagem pouco diferente das abordagens discutidas acima, portanto, pensei em compartilhá-la. Eu escrevi o código abaixo para encontrar os anagramas que funcionam em 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;
            }
         }
    }
0
Ripu Daman

Um método simples para descobrir se o testString é um anagrama da 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;
}
0
Anshul Abhinav

Desculpe, a solução é em C #, mas acho que os diferentes elementos usados ​​para chegar à solução são bastante intuitivos. Ligeira Tweak necessário para palavras hifenizadas, mas para palavras normais, deve funcionar bem.

    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;
    }
0
Sai

Alguma outra solução sem classificação.

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;
}
0
jmh
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;
}
0
Amardeep Kumar