Valid Anagram

Last updated Jul 31, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

El enunciado de este problema dice asi:

Dados dos strings s y t, devuelve verdadero si t es un anagrama de s y falso si no. Un anagrama se forma reacomodando las letras de la otra palabra, de modo que, anagram y naagram son anagramas el uno del otro.

Para solucionar este problema tenemos dos alternativas. Una usando espacio extra y otra utilizando un algoritmo de Sorting.

La solucion utilizando espacio extra se aprovecha de la estructura de datos hashmap (diccionario, pares de llave-valor). En la cual se guardan los caracteres (llave) y sus ocurrencias (valor) y posteriormente se hace una comparacion entre las ocurrencias de cada uno.

1. Checar que las longitudes de los strings sean las mismas, caso contrario, no seran anagramas.
2. Inicializar los mapas donde se guardaran las ocurrencias de cada uno de los caracteres en el string correspondiente.
3. Agregar los valores y sus ocurrencias a los mapas
4. Comparar cada uno de los caracteres entre los dos mapas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

function isAnagram(s: string, t: string): boolean {
	if (s.length !== t.length) {
		return false;
	}

	const sMap = new Map<string, number>();
	const tMap = new Map<string, number>();

	for (const c of s) {
		sMap.has(c)
			? sMap.set(c, sMap.get(c) as number + 1)
			: sMap.set(c, 1);
	}

	for (const c of t) {
		tMap.has(c)
			? tMap.set(c, tMap.get(c) as number + 1)
			: tMap.set(c, 1);
	}

	for (const k of sMap.keys()) {
		if (!tMap.has(k)) {
			return false;
		}

		if (tMap.get(k) as number !== sMap.get(k) as number) {
			return false;
		}
	}

	return true;
};

Como solucion alternativa, tambien es posible checar por la validez de los anagramas sin hacer uso de ninguna estructura de datos extra, esto se logra haciendo que ambos strings se encuentren en el mismo orden.

Para llegar a lo anterior, se utiliza un algoritmo de sorting.

1. Ordenar el primer y segundo string alfabeticamente.
2. Comparar los dos strings, si son iguales seran anagramas sino, no lo seran.

Para esto, se podrian utilizar funciones que ya se encuentren en la libreria estandar o podrias escribir la tuya propia. Para ello, se utilizaria algun Algoritmos de Sorting.

1
2
3
4
5
6

function isAnagram(s: string, t: string): boolean {
    const sSort = [...s].sort((curr: string, prev: string) => curr.charCodeAt(0) - prev.charCodeAt(0));
    const tSort = [...t].sort((curr, prev) => curr.charCodeAt(0) - prev.charCodeAt(0));

    return sSort.join("") === tSort.join("");
};