Как проверить, являются ли два слова анаграммами

Ответ 1

Самый быстрый алгоритм - сопоставить каждый из 26 английских символов с уникальным простым числом. Затем вычислите произведение строки. По основной теореме арифметики 2 строки являются анаграммами тогда и только тогда, когда их произведения одинаковы.

Ответ 2

Два слова являются анаграммами друг друга, если они содержат одинаковое количество символов и одинаковые символы. Вам нужно только отсортировать символы в лексикографическом порядке и определить, равны ли все символы в одной строке и в том же порядке, что и все символы в другой строке.

Вот пример кода. Загляните в Arrays в API, чтобы понять, что здесь происходит.

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

Ответ 3

Если вы сортируете либо массив, решение становится O (n log n). но если вы используете хэш-карту, это O (n). протестированы и работают.

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;

Ответ 4

Здесь простое быстрое решение O (n) без использования сортировки или множественных циклов или хеш-карт. Мы увеличиваем счет каждого символа в первом массиве и уменьшаем счетчик каждого символа во втором массиве. Если результирующий массив counts заполнен нулями, строки являются анаграммами. Может быть расширен, чтобы включить другие символы, увеличив размер массива counts.

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

Ответ 5

Множество людей представили решения, но я просто хочу поговорить об алгоритмической сложности некоторых общих подходов:

• Простым "сортировка символов с использованием Arrays.sort()" будет O(N log N).

• Если вы используете сортировку radix, которая сводится к O(N) с пространством O(M), где M - количество различных символов в алфавите. (Это 26 на английском языке... но теоретически мы должны рассматривать многоязычные анаграммы.)

• "Считайте символы", используя массив счетчиков, также O(N)... и быстрее, чем сортировка по методу radix, потому что вам не нужно восстанавливать отсортированную строку. Использование пространства будет O(M).

• "Считать символы" с помощью словаря, hashmap, treemap или эквивалента будет медленнее, чем подход массива, если только алфавит не огромен.

• В худшем случае, к сожалению, O(N^2) изящный подход "из простых чисел". Это потому, что для достаточно длинных слов или фраз продукт простых чисел не будет вписываться в long, Это означает, что вам нужно использовать BigInteger, а N раз умножение a BigInteger на небольшую константу - O(N^2).

  Для гипотетического большого алфавита масштабный коэффициент будет большим. Использование наихудшего пространства для хранения произведения простых чисел как BigInteger (я думаю) O(N*logM).

• Основанный на A hashcode подход обычно O(N), если слова не являются анаграммами. Если хэш-коды равны, то вам все равно нужно сделать правильный тест анаграммы. Таким образом, это не полное решение.

Ответ 6

O (n) без какой-либо сортировки и использования только одной карты.

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

и менее общее решение, но немного быстрее. Здесь вы должны поместить свой алфавит:

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

Ответ 7

Мы ходим по двум строкам равной длины и отслеживаем различия между ними. Нам все равно, каковы различия, мы просто хотим знать, имеют ли они одинаковые символы или нет. Мы можем сделать это в O (n/2) без какой-либо последующей обработки (или много простых чисел).

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

Да, этот код зависит от набора символов ASCII английского алфавита с нижним регистром, но его не следует изменять на другие языки. Вы всегда можете использовать Map [Character, Int] для отслеживания одной и той же информации, это будет только медленнее.

Ответ 8

Используя больше памяти (HashMap из не более N/2 элементов), нам не нужно сортировать строки.

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

Эта функция фактически выполняется в O (N)... вместо O (NlogN) для решения, которое сортирует строки. Если бы я предполагал, что вы собираетесь использовать только буквенные символы, я могу использовать только массив из 26 int (от a до z без акцентов или украшений) вместо хэш-карты.

Если мы определим, что: N = | один | + | два | мы делаем одну итерацию по N (один раз над одним, чтобы увеличить счетчики, и один раз, чтобы уменьшить их на два). Затем, чтобы проверить итоговые значения, мы перебираем в mose N/2.

Другие описанные алгоритмы имеют одно преимущество: они не используют дополнительную память, предполагая, что Arrays.sort использует inplace версии QuickSort или сортировку слияния. Но поскольку мы говорим об анаграммах, я предполагаю, что мы говорим о человеческих языках, поэтому слова не должны быть достаточно длинными, чтобы давать проблемы с памятью.

Ответ 9

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

}

Ответ 10

Я разработчик С++, а код ниже - на С++. Я считаю, что самый быстрый и простой способ сделать это будет следующим:

Создайте вектор ints размером 26, со всеми слотами, инициализированными до 0, и поместите каждый символ строки в соответствующую позицию в векторе. Помните, что вектор находится в алфавитном порядке, поэтому, если первая буква в строке равна z, она войдет в myvector [26]. Примечание. Это можно сделать с использованием символов ASCII, поэтому ваш код будет выглядеть примерно так:

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

Таким образом, для вставки всех элементов потребуется время O (n), так как вы проходите только один раз. Теперь вы можете сделать то же самое для второй строки, и это тоже займет время O (n). Затем вы можете сравнить два вектора, проверив, совпадают ли счетчики в каждом слоте. Если они есть, это означает, что у вас было одинаковое количество символов EACH в обеих строках и, следовательно, они являются анаграммами. Сравнение двух векторов также должно занимать время O (n), поскольку вы только проходите через него один раз.

Примечание. Код работает только для одного слова символов. Если у вас есть пробелы, цифры и символы, вы можете просто создать вектор размером 96 (символы ASCII 32-127) и вместо того, чтобы говорить - "a", вы бы сказали - "", поскольку символ пробела является первым в Список символов ASCII.

Надеюсь, это поможет. Если я где-то ошибся, оставьте комментарий.

Ответ 11

Здесь много сложных ответов. Основываясь на принятом ответе и комментарии с упоминанием проблемы 'ac' - 'bb', предполагая, что A = 65 B = 66 C = 67, мы могли бы просто использовать квадрат каждого целого числа которые представляют собой символ и решают проблему:

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

Ответ 12

Спасибо за указание сделать комментарий, комментируя, я обнаружил, что была неправильная логика. Я исправил логику и добавил комментарий для каждой части кода.

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

Ответ 13

IMHO, наиболее эффективное решение было предоставлено @Siguza, я расширил его, чтобы охватить строки с пространством, например: "Уильям Шекспир", "Я слабый спелер", "Мастер школы", "Класс"

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();

    }

Ответ 14

Подобный ответ, возможно, был опубликован на С++, здесь он снова находится на Java. Обратите внимание, что самым элегантным способом было бы использовать Trie для хранения символов в отсортированном порядке, однако, это более сложное решение. Один из способов - использовать hashset для хранения всех слов, которые мы сравниваем, а затем сравниваем их по одному. Чтобы сравнить их, создайте массив символов с индексом, представляющим значение ANCII символов (с использованием нормализатора, т.е. Значение ANCII "a" равно 97) и значение, представляющее количество совпадений этого символа. Это будет работать в O (n) времени и использовать O (m * z) пространство, где m - размер currentWord, а z - размер для сохраненногоWord, для которого мы создаем 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;
    }
}

Ответ 15

Как математик может подумать о проблеме до написания кода:

• Отношение "являются анаграммами" между строками - это отношение эквивалентности, поэтому разбивает набор всех строк на классы эквивалентности.
• Предположим, что у нас было правило выбирать представитель (crib) из каждого класса, тогда легко проверить, совпадают ли два класса, сравнивая их представителей.
• Очевидным представителем для набора строк является "наименьший < элемент по лексикографическому порядку", который легко вычислить из любого элемента путем сортировки. Например, представителем класса анаграммы, содержащего "шляпу", является "aht".

В вашем примере "школьный учитель" и "theclassroom" являются анаграммами, потому что они оба находятся в классе анаграмм с кроваткой "acehlmoorsst".

В псевдокоде:

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

Ответ 16

Пока все предлагаемые решения работают с отдельными элементами char, а не с кодовыми точками. Я хотел бы предложить два решения для правильной обработки суррогатных пар (это символы from U + 10000 до U + 10FFFF, состоящий из двух элементов char).

1) Однострочное решение O (n logn), в котором используется Java 8 CharSequence.codePoints() поток:

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

2) Менее элегантное решение O (n) (на самом деле оно будет быстрее только для длинных строк с небольшими шансами быть анаграммами):

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

Ответ 17

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

}

Ответ 18

Вот мое решение. Сначала взорвите строки в массивы char, затем отсортируйте их, а затем сравните, если они равны или нет. Я предполагаю, что временная сложность этого кода равна O (a + b).if a = b, мы можем сказать 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;

    }

Ответ 19

Некоторое другое решение без сортировки.

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

Ответ 20

Сортировка не самая лучшая. Требуется O (n) пространство и O (nlogn) время. Вместо этого создайте хэш-карту символов и подсчитайте их (увеличивайте символы, которые появляются в первой строке, и уменьшайте символы, которые появляются во второй строке). Когда какой-то счет достигает нуля, удалите его из хэша. Наконец, если две строки являются анаграммами, хэш-таблица в конце будет пустой, иначе она не будет пустой.

Пара важных заметок: (1) Игнорировать регистр букв и (2) Игнорировать пробел.

Вот подробный анализ и реализация на С#: Тестирование Если две строки являются анаграммами

Ответ 21

Простой способ выяснить, является ли testString анаграммой 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;
}

Ответ 22

Извините, решение находится на С#, но я думаю, что различные элементы, используемые для решения, являются довольно интуитивными. Небольшая настройка, требуемая для переносимых слов, но для нормальных слов она должна работать нормально.

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

Ответ 23

Я увидел, что никто не использовал подход "hashcode" для поиска анаграмм. Я обнаружил, что мой подход мало чем отличается от описанных выше подходов, поэтому он решил поделиться им. Я написал код ниже, чтобы найти анаграммы, которые работают в 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;
            }
         }
    }

Ответ 24

Вот еще один подход, использующий HashMap в 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;
}

Вот тестовый пример

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

Ответ 25

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

Ответ 26

Я столкнулся с этой концепцией HashMap в Anagrams Problem, которая очень интересна.

Вопрос: проверьте, являются ли два слова Anagrams.

Решение:

import java.util.HashMap;
import java.util.Map;

public class Anagram2 {
    public static void main(String[] args) {
        String a = "protijayiGini";
        String b = "jayiprotiiGin";
        System.out.println(checkanagrams(a,b));
    }
    static boolean checkanagrams(String a  , String  b) {
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch) +1 );
            } else {
                map.put(ch, 1);
            }
        }
        //chars sin hashmap
        for(int i = 0 ; i < b.length(); i++) {
            char ch = b.charAt(i);
            if (!map.containsKey(ch)) {
                return false;
            } else if(map.containsKey(ch)) {
                Integer frequencyOfCharacter = map.get(ch);
                if(frequencyOfCharacter == 0) {
                    return false;
                } else {
                    map.put(ch, --frequencyOfCharacter);
                }
            }
       }
       return true;
    }
}

Ответ 27

Самым простым решением со сложностью O (N) является использование Map.

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

Ответ 28

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

Ответ 29

Если мы начнем со значения 0 и XOR всех символов обеих строк, мы должны вернуть конечное значение 0, если они являются анаграммами, поскольку в анаграмме будут встречаться все символы.

static boolean areAnagram(String str1, String str2)  
{  
    // If two strings have different length  
    if (str1.length() != str2.length())  
    {  
        return false;  
    }  

    // To store the xor value  
    int value = 0;  

    for (int i = 0; i < str1.length(); i++)  
    {  
        value = value ^ (int) str1.charAt(i);  
        value = value ^ (int) str2.charAt(i);  
    }  

    return value == 0;  

}

Сложность времени: O (n)

Космическая сложность: O (1)

Ответ 30

Вы должны использовать что-то вроде этого:

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

Значение по умолчанию для isFound должно быть ложным. Просто это