найти, если два слова являются анаграммами друг друга

Question

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

Ex: string1 - abcde
string2 - abced
Ans = true
Ex: string1 - abcde
string2 - abcfed
Ans = false

Решение, которое я придумал, заключается в сортировке обеих строк и сравнении каждого символа из обеих строкдо конца любой строки. Это будет O (logn). Я ищу другой эффективный метод, который не изменяет сравниваемые 2 строки

Answer 1

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

Answer 2

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

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

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

Примечания:

1. вычисление длины при добавлении символов в массив обеспечивает прохождение каждой строки только один раз.
2. Использование массива в случае только строки ASCII оптимизирует пространство в соответствии с требованием.

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

реализация в 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)])
    }
}

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

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».