Tengo una serie de cadenas, y quiero encontrar las que tienen símbolos duplicados hasta ahora. Tengo esto:
const listOfStrings = ['aabbb','cccw','ad'] function findStringsWithDuplicates(arr) { const finalResult = []; arr.map(symbol => { for(let i = 0;i < symbol.length - 1;i++) { if(symbol[i] === symbol[i+1] && symbol[i] === symbol[i-1]) { finalResult.push(symbol) } } }) return finalResult; } findStringsWithDuplicates(listOfStrings) // [ 'aabbb', 'cccw' ] Funciona como debería, pero creo que como algoritmo es malo porque, por lo que entiendo ahora, es O(n) square por complejidad de tiempo. ¿Hay alguna forma de hacerlo solo O(n)
Puede dividir la cadena en una matriz de cada carácter individual, luego obtener los elementos únicos en esa matriz y volver a unirlos. Esto devolverá la cadena original con los caracteres duplicados eliminados.
Luego comparamos si el resultado después de unir no es igual a la cadena original o no. Si es igual, sabemos que la cadena no tiene duplicados, ya que acabamos de eliminar todos los duplicados. Si no es así, sabemos que contiene duplicados.
const listOfStrings = ['aabbb','cccw','ad'] function findStringsWithDuplicates(arr) { const finalResult = arr.filter(e => [...new Set(e.split(''))].join('') != e) return finalResult; } console.log(findStringsWithDuplicates(listOfStrings)) // [ 'aabbb', 'cccw' ] En el ejemplo anterior, e.split('') simplemente divide la cadena en una matriz de caracteres. [...new Set(arr)] obtiene los caracteres únicos y join('') une los elementos de la matriz. != luego verifica si el resultado no es igual a la cadena original.
Referencias:
Pensé en mostrarte cómo limpiar tu respuesta. Debe comenzar con un índice mayor que el primero, ya que está marcando -1 en el suyo.
No debe usar el mapa a menos que esté creando una nueva matriz a partir del contenido de la matriz que está recorriendo.
Si usa el filtro, puede deshacerse del empuje y se cerrará cuando encuentre una coincidencia, no siga comprobando.
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"] function findStringsWithDuplicates(arr) { // use filter instead of pushing to a new array return arr.filter(string => { // start loop at second index, end at second to last for (let i = 1; i < string.length - 1; i += 1) { // if we have three matches, then say it is good if (string[i - 1] === string[i] && string[i + 1] === string[i]) return true; } // if we got here, we had no matches return false; }); } console.log(findStringsWithDuplicates(listOfStrings))¿Puedes hacerlo un poco más rápido? No es una gran mejora, pero está haciendo una verificación para que pueda determinar que el segundo y el tercero son iguales, si no, puede omitirlo.
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"] function findStringsWithDuplicates(arr) { // use filter instead of pushing to a new array return arr.filter(string => { // start loop at second index, end at second to last for (let i = 1; i < string.length - 1; i += 1) { const middle = string[i]; const secondValid = string[i + 1] === middle; const firstValid = secondValid && string[i - 1] === middle; // if second match is not valid, we know next loop's iteration is not valid so jump it ahead if (!secondValid) i++; // see if we have a match, if we do exit with true else if (firstValid && secondValid) return true; } // if we got here, we had no matches return false; }); } console.log(findStringsWithDuplicates(listOfStrings))Y esta es otra forma de resolverlo con un contador.
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"] function findStringsWithDuplicates(arr) { // use filter instead of pushing to a new array return arr.filter(string => { let current = string[0]; let count = 1; let i = 1; while (i < string.length) { const next = string[i]; // is next letter the same? if (current === next) { // up the count count++; // if count is 3, exit out if (count === 3) return true; } else { //reset back to new character current = next; count = 1; } // move to next i++; } return false; }); } console.log(findStringsWithDuplicates(listOfStrings))