Если два слова являются анаграммами друг друга

Ответ 1

Подсчитайте частоту каждого символа в двух строках. Проверьте соответствие двух гистограмм. O (n), O (1) пробел (при условии ASCII) (Конечно, для Unicode все равно O (1), но таблица станет очень большой).

Ответ 2

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

К сожалению, для этого нужно использовать множественную арифметику с множественной точностью (произвольной точностью), или при использовании этого метода вы получите исключения переполнения или округления.
Для этого вы можете использовать библиотеки типа BigInteger, GMP, MPIR или IntX.

псевдокод:

prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}

primehash(string)
    Y = 1;
    foreach character in string
        Y = Y * prime[character-'a']

    return Y

isanagram(str1, str2)
    return primehash(str1)==primehash(str2)

Ответ 3

• Создайте Hashmap, где key-letter и value - frequency letter,
• для первой строки заполняет хэш (O (n))
• для второго сокращения декремента строки и удаления элемента из hashmap O (n)
• Если hashmap пуст, строка не является анаграммой.

Ответ 4

Шаги:

• проверьте длину обоих слов/строк, если они равны, а затем перейдите к проверке, чтобы анаграмма ничего не делала
• сортировать слова/строки, а затем сравнивать

КОД JAVA К ЖЕ САМОМУ:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package anagram;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 *
 * @author Sunshine
 */
public class Anagram {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        System.out.println("Enter the first string");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine().toLowerCase();
        System.out.println("Enter the Second string");
        BufferedReader br2 = new BufferedReader(new InputStreamReader(System.in));
        String s2 = br2.readLine().toLowerCase();
        char c1[] = null;
        char c2[] = null;
        if (s1.length() == s2.length()) {


            c1 = s1.toCharArray();
            c2 = s2.toCharArray();

            Arrays.sort(c1);
            Arrays.sort(c2);

            if (Arrays.equals(c1, c2)) {
                System.out.println("Both strings are equal and hence they have anagram");
            } else {
                System.out.println("Sorry No anagram in the strings entred");
            }

        } else {
            System.out.println("Sorry the string do not have anagram");
        }
    }
}

Ответ 5

С#

public static bool AreAnagrams(string s1, string s2)
{
  if (s1 == null) throw new ArgumentNullException("s1");
  if (s2 == null) throw new ArgumentNullException("s2");

  var chars = new Dictionary<char, int>();
  foreach (char c in s1)
  {
      if (!chars.ContainsKey(c))
          chars[c] = 0;
      chars[c]++;
  }
  foreach (char c in s2)
  {
      if (!chars.ContainsKey(c))
          return false;
      chars[c]--;
  }

  return chars.Values.All(i => i == 0);
}

Некоторые тесты:

[TestMethod]
public void TestAnagrams()
{
  Assert.IsTrue(StringUtil.AreAnagrams("anagramm", "nagaramm"));
  Assert.IsTrue(StringUtil.AreAnagrams("anzagramm", "nagarzamm"));
  Assert.IsTrue(StringUtil.AreAnagrams("anz121agramm", "nag12arz1amm"));
  Assert.IsFalse(StringUtil.AreAnagrams("anagram", "nagaramm"));
  Assert.IsFalse(StringUtil.AreAnagrams("nzagramm", "nagarzamm"));
  Assert.IsFalse(StringUtil.AreAnagrams("anzagramm", "nag12arz1amm"));
}

Ответ 6

Код, чтобы найти, являются ли два слова анаграммами:

Логика объяснялась уже в нескольких ответах, а некоторые просили код. Это решение дает результат в O (n) времени.

Этот подход подсчитывает количество вхождений каждого символа и сохраняет его в соответствующем местоположении ASCII для каждой строки. А затем сравните два массива. Если он не является равным, данные строки не являются анаграммами.

public boolean isAnagram(String str1, String str2)
{
    //To get the no of occurrences of each character and store it in their ASCII location
    int[] strCountArr1=getASCIICountArr(str1);
    int[] strCountArr2=getASCIICountArr(str2);

    //To Test whether the two arrays have the same count of characters. Array size 256 since ASCII 256 unique values
    for(int i=0;i<256;i++)
    {
        if(strCountArr1[i]!=strCountArr2[i])
            return false;
    }
    return true;
}

public int[] getASCIICountArr(String str)
{
    char c;
    //Array size 256 for ASCII
    int[] strCountArr=new int[256];
    for(int i=0;i<str.length();i++)
    {
        c=str.charAt(i); 
        c=Character.toUpperCase(c);// If both the cases are considered to be the same
        strCountArr[(int)c]++; //To increment the count in the character ASCII location
    }
    return strCountArr;
}

Ответ 7

Использование хэш-карты ASCII, которая позволяет O (1) искать для каждого char.

Приведенный выше пример java преобразуется в нижний регистр, который кажется неполным. У меня есть пример в C, который просто инициализирует массив хеш-карт для значения ASCII до '-1'

Если строка 2 отличается по длине, чем строка 1, анаграммы

Else, мы обновляем соответствующие значения хэш-карты до 0 для каждого char в строке1 и string2

Затем для каждого char в строке1 мы обновляем счет в хэш-карте. Аналогично, мы уменьшаем значение count для каждого char в строке2.

Результат должен иметь значения, равные 0 для каждого char, если они являются анаграммами. если нет, некоторое положительное значение, заданное строкой1, остается

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAYMAX 128

#define True        1
#define False       0

int isAnagram(const char *string1, 
            const char *string2) {

    int str1len = strlen(string1);
    int str2len = strlen(string2);

    if (str1len != str2len) /* Simple string length test */
        return False;

    int * ascii_hashtbl = (int * ) malloc((sizeof(int) * ARRAYMAX));
    if (ascii_hashtbl == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return -1;
    }
    memset((void *)ascii_hashtbl, -1, sizeof(int) * ARRAYMAX);
    int index = 0;
    while (index < str1len) { /* Populate hash_table for each ASCII value 
                                in string1*/
        ascii_hashtbl[(int)string1[index]] = 0;
        ascii_hashtbl[(int)string2[index]] = 0;
        index++;
    }
    index = index - 1;
    while (index >= 0) {
        ascii_hashtbl[(int)string1[index]]++; /* Increment something */
        ascii_hashtbl[(int)string2[index]]--; /* Decrement something */
        index--;
    }
    /* Use hash_table to compare string2 */
    index = 0;
    while (index < str1len) {
        if (ascii_hashtbl[(int)string1[index]] != 0) {
            /* some char is missing in string2 from string1 */
            free(ascii_hashtbl);
            ascii_hashtbl = NULL;
            return False;
        }
        index++;
    }
    free(ascii_hashtbl);
    ascii_hashtbl = NULL;
    return True;
}

int main () {
    char array1[ARRAYMAX], array2[ARRAYMAX];
    int flag;

    printf("Enter the string\n");
    fgets(array1, ARRAYMAX, stdin);
    printf("Enter another string\n");
    fgets(array2, ARRAYMAX, stdin);

    array1[strcspn(array1, "\r\n")] = 0;
    array2[strcspn(array2, "\r\n")] = 0;
    flag = isAnagram(array1, array2);
    if (flag == 1)
        printf("%s and %s are anagrams.\n", array1, array2);
    else if (flag == 0)
        printf("%s and %s are not anagrams.\n", array1, array2);

    return 0;
}

Ответ 8

Хорошо, что вы, вероятно, можете улучшить лучший случай и средний случай, по существу, просто проверив длину сначала, а затем быструю контрольную сумму на цифрах (не что-то сложное, так как это, вероятно, будет хуже, чем сортировка, просто суммирование порядковых номеров значения), затем сортировка, затем сравнение.

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

Ответ 9

Как насчет этого?

a = "lai d"
b = "di al"
sorteda = []
sortedb = []
for i in a:
    if i != " ":
        sorteda.append(i)
        if c == len(b):
            for x in b:
                c -= 1
                if x != " ":
                    sortedb.append(x)
sorteda.sort(key = str.lower)
sortedb.sort(key = str.lower)

print sortedb
print sorteda

print sortedb == sorteda

Ответ 10

Как насчет Xor'ing обеих строк??? Это определенно будет O (n)

char* arr1="ab cde";
int n1=strlen(arr1);
char* arr2="edcb a";
int n2=strlen(arr2);
// to check for anagram;
int c=0;
int i=0, j=0;   
if(n1!=n2) 
  printf("\nNot anagram");
else {
   while(i<n1 || j<n2)
   {
       c^= ((int)arr1[i] ^ (int)arr2[j]);
       i++;
       j++;
   }
}

if(c==0) {
    printf("\nAnagram");
}
else printf("\nNot anagram");

}

Ответ 11

Для известных (и малых) наборов допустимых букв (например, ASCII) используется таблица со счетами, связанными с каждой допустимой буквой. Приращения первой строки увеличиваются, количество секунд уменьшается. Наконец, итерации по таблице, чтобы увидеть, все ли отсчеты равны нулю (строки являются анаграммами) или существуют ненулевые значения (строки не являются анаграммами). Не забудьте преобразовать все символы в верхний регистр (или в нижний регистр, все равно) и игнорировать пробелы.

Для большого набора допустимых букв, например Unicode, не используйте таблицу, а используйте хеш-таблицу. Он имеет O (1) время для добавления, запроса и удаления и O (n) пространства. Буквы от первого приращения строки, буквы из второго значения декремента строки. Граф, который становится равным нулю, удаляется из хеш-таблицы. Строки являются анаграммами, если в конце хеш-таблица пуста. Альтернативно, поиск заканчивается отрицательным результатом, как только любой счет становится отрицательным.

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

Ответ 12

static bool IsAnagram(string s1, string s2)
        {

            if (s1.Length != s2.Length)
                return false;
            else
            {
                int sum1 = 0;
                for (int i = 0; i < s1.Length; i++)
                sum1 += (int)s1[i]-(int)s2[i];
                if (sum1 == 0)
                    return true;
                else
                    return false;
            }
        }

Ответ 13

Если строки имеют только символы ASCII:

• создать массив длиной 256
• пересечь первую строку и счетчик приращений в массиве по значению index = ascii символа. также продолжайте считать символы, чтобы найти длину, когда вы достигнете конца строки
• пересечь вторую строку и счетчик декремента в массиве со значением индекса = ascii символа. Если значение имеет значение 0 до декремента, верните false, поскольку строки не являются анаграммами. также отслеживать длину этой второй строки.
• в конце обхода строки, если длины двух равны, верните true, else, верните false.

Если строка может содержать символы Юникода, используйте хэш-карту вместо массива, чтобы отслеживать частоту. Остальная часть алгоритма остается такой же.

Примечания:

• вычисление длины при добавлении символов в массив гарантирует, что мы пересекаем каждую строку только один раз.
• Использование массива в случае только строки ASCII оптимизирует пространство на основе требования.

Ответ 14

Я предполагаю, что ваш алгоритм сортировки на самом деле не O (log n), не так ли?

Лучшее, что вы можете получить, это O (n) для вашего алгоритма, потому что вы должны проверять каждый символ.

Вы можете использовать две таблицы для хранения отсчетов каждой буквы в каждом слове, заполнить ее O (n) и сравнить ее с O (1).

Ответ 15

Кажется, что и следующая реализация работает, можете ли вы проверить?

int histogram[256] = {0};
for (int i = 0; i < strlen(str1); ++i) {
   /* Just inc and dec every char count and
    * check the histogram against 0 in the 2nd loop */
   ++histo[str1[i]];
   --histo[str2[i]];
}

for (int i = 0; i < 256; ++i) {
   if (histo[i] != 0)
     return 0; /* not an anagram */
}

return 1; /* an anagram */

Ответ 16

/* Program to find the strings are anagram or not*/
/* Author Senthilkumar M*/

Eg. 
    Anagram:
    str1 = stackoverflow
    str2 = overflowstack

    Not anagram:`enter code here`
    str1 = stackforflow
    str2 = stacknotflow

int is_anagram(char *str1, char *str2)
{
        int l1 = strlen(str1);
        int l2 = strlen(str2);
        int s1 = 0, s2 = 0;
        int i = 0;

        /* if both the string are not equal it is not anagram*/
        if(l1 != l2) {
                return 0;
        }
        /* sum up the character in the strings 
           if the total sum of the two strings is not equal
           it is not anagram */
        for( i = 0; i < l1; i++) {
                s1 += str1[i];
                s2 += str2[i];
        }
        if(s1 != s2) {
                return 0;
        }
        return 1;
}

Ответ 17

Если обе строки имеют равную длину, продолжайте, если нет, то строки не являются анаграммами.

Итерации каждой строки при суммировании ординалов каждого символа. Если суммы равны, то строки являются анаграммами.

Пример:

    public Boolean AreAnagrams(String inOne, String inTwo) {

        bool result = false;

        if(inOne.Length == inTwo.Length) {

            int sumOne = 0;
            int sumTwo = 0;

            for(int i = 0; i < inOne.Length; i++) {

                sumOne += (int)inOne[i];
                sumTwo += (int)inTwo[i];
            }

            result = sumOne == sumTwo;
        }

        return result;
    }

Ответ 18

в Swift 3:

func areAnagrams(_ str1: String, _ str2: String) -> Bool {
    return dictionaryMap(forString: str1) == dictionaryMap(forString: str2)
}

func dictionaryMap(forString str: String) -> [String : Int] {
    var dict : [String : Int] = [:]
    for var i in 0..<str.characters.count {
        if let count = dict[str[i]] {
            dict[str[i]] = count + 1
        }else {
            dict[str[i]] = 1
        }
    }        
    return dict
}
//To easily subscript characters
extension String {
    subscript(i: Int) -> String {
        return String(self[index(startIndex, offsetBy: i)])
    }
}

Ответ 19

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * --------------------------------------------------------------------------
 * Finding Anagrams in the given dictionary. Anagrams are words that can be
 * formed from other words Ex :The word "words" can be formed using the word
 * "sword"
 * --------------------------------------------------------------------------
 * Input : if choose option 2 first enter no of word want to compare second
 * enter word ex:
 * 
 * Enter choice : 1:To use Test Cases 2: To give input 2 Enter the number of
 * words in dictionary 
 * 6
 * viq 
 * khan
 * zee 
 * khan
 * am
 *    
 * Dictionary : [ viq khan zee khan am]
 * Anagrams 1:[khan, khan]
 * 
 */
public class Anagrams {

    public static void main(String args[]) {
        // User Input or just use the testCases
        int choice;
        @SuppressWarnings("resource")
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter choice : \n1:To use Test Cases 2: To give input");
        choice = scan.nextInt();
        switch (choice) {
        case 1:
            testCaseRunner();
            break;
        case 2:
            userInput();
        default:
            break;
        }
    }

    private static void userInput() {
        @SuppressWarnings("resource")
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of words in dictionary");
        int number = scan.nextInt();
        String dictionary[] = new String[number];
        //
        for (int i = 0; i < number; i++) {
            dictionary[i] = scan.nextLine();
        }
        printAnagramsIn(dictionary);

    }

    /**
     * provides a some number of dictionary of words
     */
    private static void testCaseRunner() {

        String dictionary[][] = { { "abc", "cde", "asfs", "cba", "edcs", "name" },
                { "name", "mane", "string", "trings", "embe" } };
        for (int i = 0; i < dictionary.length; i++) {
            printAnagramsIn(dictionary[i]);
        }
    }

    /**
     * Prints the set of anagrams found the give dictionary
     * 
     * logic is sorting the characters in the given word and hashing them to the
     * word. Data Structure: Hash[sortedChars] = word
     */
    private static void printAnagramsIn(String[] dictionary) {
        System.out.print("Dictionary : [");// + dictionary);
        for (String each : dictionary) {
            System.out.print(each + " ");
        }
        System.out.println("]");
        //

        Map<String, ArrayList<String>> map = new LinkedHashMap<String, ArrayList<String>>();
        // review comment: naming convention: dictionary contains 'word' not
        // 'each'
        for (String each : dictionary) {
            char[] sortedWord = each.toCharArray();
            // sort dic value
            Arrays.sort(sortedWord);
            //input word
            String sortedString = new String(sortedWord);
            //
            ArrayList<String> list = new ArrayList<String>();
            if (map.keySet().contains(sortedString)) {
                list = map.get(sortedString);
            }
            list.add(each);
            map.put(sortedString, list);
        }
        // print anagram
        int i = 1;
        for (String each : map.keySet()) {
            if (map.get(each).size() != 1) {
                System.out.println("Anagrams " + i + ":" + map.get(each));
                i++;
            }
        }
    }
}

Ответ 20

в java мы также можем сделать это так и свою очень простую логику

import java.util.*;

class Anagram
{
 public static void main(String args[]) throws Exception
 {
  Boolean FLAG=true;

  Scanner sc= new Scanner(System.in);

  System.out.println("Enter 1st string");

  String s1=sc.nextLine();

  System.out.println("Enter 2nd string");

  String s2=sc.nextLine();

  int i,j;
  i=s1.length();
  j=s2.length();

  if(i==j)
  {
   for(int k=0;k<i;k++)
   {
    for(int l=0;l<i;l++)
    {
     if(s1.charAt(k)==s2.charAt(l))
     {
      FLAG=true;
      break;
     }
     else
     FLAG=false;
    }
   }
  }
  else
  FLAG=false;
  if(FLAG)
  System.out.println("Given Strings are anagrams");
  else
  System.out.println("Given Strings are not anagrams");
 }
}

Ответ 21

Как насчет преобразования в значение int символа и суммирования:

Если значение суммы равно, то они являются анаграммами друг к другу.

def are_anagram1(s1, s2):
    return [False, True][sum([ord(x) for x in s1]) == sum([ord(x) for x in s2])]

s1 = 'james'
s2 = 'amesj'
print are_anagram1(s1,s2)

Это решение работает только для "A" - "Z" и "a" - "z".