¡Espero que todo esté bien por tu parte!
Encontré un problema de secuencia interesante y he estado luchando para resolverlo: "Encuentre la secuencia más común en la matriz de cadenas con una cantidad específica de caracteres".
Entrada: (["abc", "usbc", "bcde"], 2) Salida: "bc"
Entrada: (["terrific, specific"], 4) Salida: "ific"
Esto es lo que tengo hasta ahora:
function commonSubstring(array, length) { let popular = ''; let seq = [] let map = {} for (let i = 0; i < array.length; i++) { for (let j = 0; j < array[i].length; j++) { const str = array[i].slice(j, j+length) if (str.length === length && array[i].includes(str)) { seq.push(str) } if (array[i].includes(seq[j]) && !map[seq[j]]) { map[seq[j]] = 1 // console.log(seq[j]) } else { map[seq[j]]++ j++ } } } console.log(map) return popular }Lo que estaba tratando de hacer es revisar cada elemento de la cadena y encontrar secuencias comunes y agregué un mapa para tener un sistema de puntos, luego finalmente encontré la clave que tiene la mayor cantidad de puntos y devolví esa clave.
Sinceramente, estoy un poco perdido. ¿Cómo resuelvo eficientemente este problema?
¡Gracias!
aquí hay una solución usando un bucle for y una llamada recursiva
const getSequence = (list, length, check) => { if(!list.length || (check && check.length < length)) { return false; } let result = check || list[0]; //setting first item as a result let found = true; let i; for(i = 1; i<list.length; i++) { if(list[i].indexOf(result.substring(0, length)) == -1) { found = false; break; } } if(!found) { let val = getSequence(list, length, result.substring(1, result.length)) //calling same function by removing first char if(val) { return val; } } else { return result.substring(0, length); } } console.log(getSequence(["abc", "usbcj", "bcdeh"], 2)) console.log(getSequence(["terrific", "specific"], 4)) console.log(getSequence(["test", "text"], 2))Esta es una modificación de su código que implementa las sugerencias en mi comentario anterior:
También agregué la búsqueda máxima para que devuelva la respuesta:
function commonSubstring(array, length) { let popular = ''; let seq = [] let map = {} for (let i = 0; i < array.length; i++) { for (let j = 0; j < array[i].length - length + 1; j++) { const str = array[i].slice(j, j+length) if (!map[str]) { map[str] = 1 } else { map[str]++ } } } // console.log(map) let maxv = 0; for(let prop in map) { if(map[prop] > maxv) { popular = prop; maxv = map[prop]; } } return popular } console.log(commonSubstring(["abc", "usbcj", "bcdeh"], 2)) console.log(commonSubstring(["terrific", "specific"], 4)) console.log(commonSubstring(["test", "text"], 2)) Esto se ejecuta en O(n*m) donde n es el número total de caracteres de entrada y m es el parámetro de longitud. Hasta donde sé, esta es la mejor complejidad de CPU que puede obtener para este problema. En cuanto a la eficiencia de la implementación, debería estar bastante cerca de lo mejor posible.