Group Anagrams

Last updated Aug 1, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Este es un problema un poco mas complejo, sin embargo, sirve para medir que tanto conoces los fundamentales de DSA. El problema dicta asi:

Dada una lista de strings strs agrupa juntos las palabras que sean anagramas dentro de una lista. Finalmente, retorna una lista que contenga todas las listas de palabras que forman diferentes anagramas. Por ejemplo, dado ["eat", "tea", "mae"] el resultado seria: [["eat", "tea"], ["mae"]].

Para resolver el problema existen dos soluciones posibles. Que pueden llegar a ser mas complejas o mas sencillas dependiendo del lenguaje que estes usando para implementar el problema.

La primer solucion y la mas sencilla globalmente es utilizar un algoritmo de sorting. La solucion se ve algo asi:

1. Crear un mapa que contendra como llave, un string ordenado alfabeticamente y como valor una lista de strings que encajan con dicha llave ordenada
2. Iterar sobre cada uno de los strings
3. Ordenar el string alfabeticamente
4. En caso de que este exista como llave dentro del mapa simplemente añadir el string original (sin ordenar) al valor (lista) de dicha llave.
5. En caso de que no exista la llave, agregarla al mapa inicializando la lista de valor con el string actual.
6. Finalmente retornar en una lista los valores de los strings

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function groupAnagrams(strs: string[]): string[][] {
	const map = new Map<string, string[]>();
	for (const s of strs) {
		const o = [...s].sort((curr, prev) => curr.charCodeAt(0) - prev.charCodeAt(0)).join("");
		map.has(o)
			? map.set(o, [...map.get(o) as string[], s])
			: map.set(o, [s]);
	}

	return [...map.values()];
}

Aprovechando que el problema dicta que las letras unicamente son minusculas (limitado a 26 caracteres) podemos evitar utilizar un algoritmo de sorting y en su lugar utilizar una lista como llave, lista la cual tendra las ocurrencias de cada caracter la cantidad de veces que este ocurre y como valor nuevamente la lista de strings que encajan con dicha llave.

1. Crear un mapa que contendra como llave; una lista de numeros, en la cual el index ith corresponde a la letra en la posicion a + ith. Por tanto: 0 = a, 1 = b, 2 = c, 3 = d, etc… y como valor la lista de strings que encajan con dicha llave
2. Iterar sobre cada uno de los strings
3. Inicializar una lista con 26 de longitud y un valor inicial de 0 en cada uno de ellos
4. Iterar sobre cada caracter, e ir actualizando la lista con las ocurrencias de cada uno
5. En caso de que este exista como llave dentro del mapa simplemente añadir el string original (sin ordenar) al valor (lista) de dicha llave.
6. En caso de que no exista la llave, agregarla al mapa inicializando la lista de valor con el string actual.
7. Finalmente retornar en una lista los valores de los strings

El codigo en TypeScript es un poco tricky aqui, particularmente al:

• Inicializar el array desde el constructor del objeto global Array
• El uso del metodo toString() debido a que la comparacion en TS ocurre por referencias, siempre las referencias seran diferentes a pesar que los elementos dentro de la lista sean los mismos, es por esto que no se pueden usar como keys de un mapa.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function groupAnagrams(strs: string[]): string[][] {
	const map = new Map<string, string[]>(); //
	for (const s of strs) {
		const sl: number[] = Array.from({ length: 26 }, () => 0); // Se inicializa un array con longitud 26, la funcion que se pasa es un inicializador, en este caso, inicializa todos los elementos a 0
		for (const c of s) {
			sl[c.charCodeAt(0) - "a".charCodeAt(0)]++;
		}

		const sKey = sl.toString();
		map.has(sKey)
			? map.set(sKey, [...map.get(sKey) as string[], s])
			: map.set(sKey, [s]);
	}

	return [...map.values()];
}