algorithm - algoritmo - anagrama en c++
encontrar si dos palabras son anagramas el uno del otro (22)
Estoy buscando un método para encontrar si dos cadenas son anagramas entre sí.
Ex: string1 - abcde
string2 - abced
Ans = true
Ex: string1 - abcde
string2 - abcfed
Ans = false
la solución que se me ocurrió fue para ordenar ambas cadenas y comparar cada carácter de ambas cadenas hasta el final de cualquiera de las cadenas. Sería O (logn). Estoy buscando otro método eficiente que no cambie el 2 cuerdas que se comparan
- Cree un Hashmap donde la clave - letra y valor - frecuencia de letra,
- para la primera cadena, rellene el hashmap (O (n))
- para el segundo conteo de decrementos de cadena y eliminar elemento de hashmap O (n)
- si hashmap está vacío, la cadena es anagrama; de lo contrario, no.
¿Qué le parece convertir en el valor int del personaje y resumirlo?
Si el valor de sum es igual, entonces son anagramas entre sí.
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)
Esta solución solo funciona para ''A'' a ''Z'' y ''a'' a ''z''.
¿Qué tal Xor''ing las dos cuerdas? Esto definitivamente será de 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");
}
¿Qué tal esto?
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
Bueno, probablemente puedas mejorar el mejor caso y el promedio de casos básicamente al verificar la longitud primero, luego una suma de comprobación rápida en los dígitos (no algo complejo, ya que probablemente será peor que el ordenamiento, solo una suma de valores ordinales), luego ordena, luego compara.
Si las cadenas son muy cortas, el costo de la suma de comprobación no será muy diferente al ordenado en muchos idiomas.
Cuenta la frecuencia de cada personaje en las dos cadenas. Verifique si los dos histogramas coinciden. O (n) tiempo, O (1) espacio (asumiendo ASCII) (Por supuesto, sigue siendo O (1) espacio para Unicode pero la tabla será muy grande).
DO#
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);
}
Algunas pruebas:
[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"));
}
Hagamos una pregunta: Dadas dos cadenas s y t, escribe una función para determinar si t es un anagrama de s.
Por ejemplo, s = "anagrama", t = "nagaram", devuelve verdadero. s = "rata", t = "carro", devuelve falso.
Método 1 (Usando HashMap):
public class Method1 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
Map<Character ,Integer> map = new HashMap<>();
for( char c : a.toCharArray()) {
map.put(c, map.getOrDefault(c, 0 ) + 1 );
}
for(char c : b.toCharArray()) {
int count = map.getOrDefault(c, 0);
if(count == 0 ) {return false ; }
else {map.put(c, count - 1 ) ; }
}
return true;
}
}
Método 2:
public class Method2 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b));// output=> true
}
private static boolean isAnagram(String a, String b) {
int[] alphabet = new int[26];
for(int i = 0 ; i < a.length() ;i++) {
alphabet[a.charAt(i) - ''a'']++ ;
}
for (int i = 0; i < b.length(); i++) {
alphabet[b.charAt(i) - ''a'']-- ;
}
for( int w : alphabet ) {
if(w != 0 ) {return false;}
}
return true;
}
}
Método 3:
public class Mathod3 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
char[] ca = a.toCharArray() ;
char[] cb = b.toCharArray();
Arrays.sort( ca );
Arrays.sort( cb );
return Arrays.equals(ca , cb );
}
}
Método 4:
public class Method4 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
//String c = "gini";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
Map<Integer, Integer> map = new HashMap<>();
a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
//System.out.println(map.values());
for(int count : map.values()) {
if (count<0) return false;
}
return true;
}
}
En Python:
def areAnagram(a, b):
if len(a) != len(b): return False
count1 = [0] * 256
count2 = [0] * 256
for i in a:count1[ord(i)] += 1
for i in b:count2[ord(i)] += 1
for i in range(256):
if(count1[i] != count2[i]):return False
return True
str1 = "Giniiii"
str2 = "Protijayi"
print(areAnagram(str1, str2))
Los pasos son:
- verifique la longitud de ambas palabras / cadenas si son iguales, entonces solo proceda a verificar el anagrama, de lo contrario, no haga nada
- ordenar las palabras / cadenas y luego comparar
CÓDIGO JAVA AL MISMO:
/*
* 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");
}
}
}
Obtenga una tabla de números primos, suficiente para asignar cada primo a cada personaje. Así que comienza desde 1, pasando por línea, multiplica el número por el primo que representa el personaje actual. El número que obtendrá solo dependerá de los caracteres de la cadena, pero no de su orden, y cada conjunto único de caracteres corresponde a un número único, ya que cualquier número puede tenerse en cuenta de una sola manera. Entonces puedes comparar dos números para decir si las cadenas son anagramas entre sí.
Lamentablemente, debe usar la aritmética de enteros de precisión múltiple (precisión arbitraria) para hacer esto, o obtendrá excepciones de desbordamiento o redondeo al usar este método.
Para esto puede usar bibliotecas como BigInteger , GMP , MPIR o IntX .
Pseudocódigo:
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)
Para juegos conocidos (y pequeños) de letras válidas (por ejemplo, ASCII), use una tabla con los recuentos asociados con cada letra válida. La primera cuerda incrementa los conteos, la segunda cadena disminuye los conteos. Finalmente, recorra la tabla para ver si todos los recuentos son cero (las cadenas son anagramas) o si existen valores distintos de cero (las cadenas no son anagramas). Asegúrese de convertir todos los caracteres a mayúsculas (o minúsculas, todos iguales) e ignorar el espacio en blanco.
Para un gran conjunto de letras válidas, como Unicode, no use la tabla, sino más bien use una tabla hash. Tiene O (1) tiempo para agregar, consultar y eliminar y O (n) espacio. Cartas del recuento de incrementos de la primera cuerda, letras del recuento de decrementos de la segunda cuerda. El recuento que se convierte en cero se elimina de la tabla hash. Las cadenas son anagramas si al final la tabla hash está vacía. Alternativamente, la búsqueda termina con resultado negativo tan pronto como cualquier recuento se vuelve negativo.
Aquí está la explicación detallada y la implementación en C #: Prueba si dos cadenas son Anagramas
Parece que la siguiente implementación también funciona, ¿puedes verificar?
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 */
Si ambas cadenas tienen la misma longitud proceden, si no, las cadenas no son anagramas.
Iterar cada cadena mientras se suman los ordinales de cada carácter. Si las sumas son iguales, las cadenas son anagramas.
Ejemplo:
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;
}
Si las cadenas tienen solo caracteres ASCII:
- crear una matriz de 256 de longitud
- atraviesa la primera cuerda e incrementa el contador en la matriz en el índice = valor ascii del personaje. también sigue contando caracteres para encontrar la longitud cuando llegas al final de la cadena
- atraviesa la segunda cuerda y decrementa el contador en la matriz en el índice = valor ascii del personaje. Si el valor es alguna vez 0 antes de decrementar, devuelva falso ya que las cadenas no son anagramas. también, lleve un registro de la longitud de esta segunda cuerda.
- al final del recorrido de la cuerda, si las longitudes de las dos son iguales, devuelve verdadero, de lo contrario, devuelve falso.
Si la cadena puede tener caracteres Unicode, utilice un mapa hash en lugar de una matriz para realizar un seguimiento de la frecuencia. El resto del algoritmo permanece igual.
Notas:
- calcular la longitud al agregar caracteres a la matriz garantiza que recorramos cada cadena solo una vez.
- El uso de una matriz en el caso de una cadena ASCII only optimiza el espacio según el requisito.
Supongo que tu algoritmo de clasificación no es realmente O (log n), ¿o sí?
Lo mejor que puede obtener es O (n) para su algoritmo, porque debe verificar cada carácter.
Puede usar dos tablas para almacenar los recuentos de cada letra en cada palabra, llenarlo con O (n) y compararlo con O (1).
Usando un hash-map ASCII que permite la búsqueda O (1) para cada char.
El ejemplo de java mencionado anteriormente se está convirtiendo a minúsculas que parece incompleto. Tengo un ejemplo en C que simplemente inicializa una matriz de hash-map para valores ASCII a ''-1''
Si string2 es diferente en longitud que la cadena 1, no hay anagramas
De lo contrario, actualizamos los valores adecuados de hash-map a 0 para cada char en string1 y string2
Luego, para cada char en string1, actualizamos el recuento en hash-map. Similarmente, disminuimos el valor del conteo para cada char en string2.
El resultado debe tener valores establecidos en 0 para cada carácter si son anagramas. si no, queda algún valor positivo establecido por string1
#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;
}
en java también podemos hacerlo así y su lógica muy simple
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");
}
}
implementación en 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)])
}
}
Codifique para encontrar si dos palabras son anagramas:
La lógica ya se explicó en pocas respuestas y pocas pidieron el código. Esta solución produce el resultado en el tiempo O (n).
Este enfoque cuenta el número de ocurrencias de cada carácter y lo almacena en la ubicación ASCII respectiva para cada cadena. Y luego compara los dos recuentos de matriz. Si no es igual, las cadenas dadas no son anagramas.
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''s ASCII location
}
return strCountArr;
}
/* Program to find the strings are anagram or not*/
/* Author Senthilkumar M*/
Eg.
Anagram:
str1 =
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;
}
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++;
}
}
}
}
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;
}
}