Я ищу способ найти, являются ли две строки анаграммами друг друга.
Ex: string1 - abcde
string2 - abced
Ans = true
Ex: string1 - abcde
string2 - abcfed
Ans = false
Решение, с которым я столкнулся, - это сортировать строки и сравнивать каждый символ из обеих строк до конца любой строки. Это будет O (logn). Я ищу другой эффективный метод, t измените сравниваемые 2 строки
Подсчитайте частоту каждого символа в двух строках. Проверьте соответствие двух гистограмм. O (n), O (1) пробел (при условии ASCII) (Конечно, для Unicode все равно O (1), но таблица станет очень большой).
Получить таблицу простых чисел, достаточную для сопоставления каждого штриха каждому символу. Итак, начните с 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)
Шаги:
КОД 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");
}
}
}
С#
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"));
}
Код, чтобы найти, являются ли два слова анаграммами:
Логика объяснялась уже в нескольких ответах, а некоторые просили код. Это решение дает результат в 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;
}
Использование хэш-карты 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;
}
Хорошо, что вы, вероятно, можете улучшить лучший случай и средний случай, по существу, просто проверив длину сначала, а затем быструю контрольную сумму на цифрах (не что-то сложное, так как это, вероятно, будет хуже, чем сортировка, просто суммирование порядковых номеров значения), затем сортировка, затем сравнение.
Если строки очень короткие, сумма контрольной суммы не будет сильно отличаться от сортировки на многих языках.
Как насчет этого?
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
Как насчет 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");
}
Для известных (и малых) наборов допустимых букв (например, ASCII) используется таблица со счетами, связанными с каждой допустимой буквой. Приращения первой строки увеличиваются, количество секунд уменьшается. Наконец, итерации по таблице, чтобы увидеть, все ли отсчеты равны нулю (строки являются анаграммами) или существуют ненулевые значения (строки не являются анаграммами). Не забудьте преобразовать все символы в верхний регистр (или в нижний регистр, все равно) и игнорировать пробелы.
Для большого набора допустимых букв, например Unicode, не используйте таблицу, а используйте хеш-таблицу. Он имеет O (1) время для добавления, запроса и удаления и O (n) пространства. Буквы от первого приращения строки, буквы из второго значения декремента строки. Граф, который становится равным нулю, удаляется из хеш-таблицы. Строки являются анаграммами, если в конце хеш-таблица пуста. Альтернативно, поиск заканчивается отрицательным результатом, как только любой счет становится отрицательным.
Вот подробное объяснение и реализация в С#: Тестирование Если две строки являются анаграммами
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;
}
}
Если строки имеют только символы ASCII:
Если строка может содержать символы Юникода, используйте хэш-карту вместо массива, чтобы отслеживать частоту. Остальная часть алгоритма остается такой же.
Примечания:
Я предполагаю, что ваш алгоритм сортировки на самом деле не O (log n), не так ли?
Лучшее, что вы можете получить, это O (n) для вашего алгоритма, потому что вы должны проверять каждый символ.
Вы можете использовать две таблицы для хранения отсчетов каждой буквы в каждом слове, заполнить ее O (n) и сравнить ее с O (1).
Кажется, что и следующая реализация работает, можете ли вы проверить?
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 */
/* 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;
}
Если обе строки имеют равную длину, продолжайте, если нет, то строки не являются анаграммами.
Итерации каждой строки при суммировании ординалов каждого символа. Если суммы равны, то строки являются анаграммами.
Пример:
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;
}
в 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)])
}
}
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++;
}
}
}
}
в 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");
}
}
Как насчет преобразования в значение 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".