Dada una matriz de cadenas, devuelve todos los grupos de cadenas que son anagramas.
Un anagrama es un tipo de juego de palabras, el resultado de reorganizar las letras de una palabra o frase para producir una nueva palabra o frase, usando todas las letras originales exactamente una vez; por ejemplo, Torchwood se puede reorganizar en Doctor Who.
Solución Java
Si dos cadenas son anagramas entre sí, su secuencia ordenada es la misma.
public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> result = new ArrayList<List<String>>(); HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); for(String str: strs){ char[] arr = new char[26]; for(int i=0; i<str.length(); i++){ arr[str.charAt(i)-'a']++; } String ns = new String(arr); if(map.containsKey(ns)){ map.get(ns).add(str); }else{ ArrayList<String> al = new ArrayList<String>(); al.add(str); map.put(ns, al); } } result.addAll(map.values()); return result; } |
Complejidad del tiempo
Si la longitud promedio de los verbos es my la longitud de la matriz es n, entonces el tiempo es O (n * m).