Estoy tratando de resolver el desafío del código Leet 14. Prefijo común más largo :
Escriba una función para encontrar la cadena de prefijo común más larga entre una matriz de cadenas.
Si no hay un prefijo común, devuelve una cadena vacía
"".Ejemplo 1:
Input: strs = ["flower","flow","flight"] Output: "fl"Ejemplo 2:
Input: strs = ["dog","racecar","car"] Output: ""Explicación: No existe un prefijo común entre las cadenas de entrada.
Restricciones:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]consta solo de letras minúsculas en inglés.
let strs = ["flower", "flow", "flight"]; var longestCommonPrefix = function (strs) { for (let i = 0; i < strs.length; i++) { for (let j = 0; j < strs[i].length; j++) { // console.log(strs[i+2][j]); if (strs[i][j] == strs[i + 1][j] && strs[i + 1][j] ==strs[i + 2][j]) { return (strs[i][j]); } else { return "0"; } } } }; console.log(longestCommonPrefix(strs)); Salida: f
¿Cómo puedo iterar sobre cada carácter y verificar si es el mismo y luego ir al siguiente y si falla, se devolverá el prefijo común más largo?
Como el prefijo común más largo debe aparecer en cada cadena de la matriz, puede iterar sobre la longitud y verificar si todas las palabras tienen el mismo carácter en ese índice hasta que encuentre una diferencia.
function prefix(words){ // check border cases size 1 array and empty first word) if (!words[0] || words.length == 1) return words[0] || ""; let i = 0; // while all words have the same character at position i, increment i while(words[0][i] && words.every(w => w[i] === words[0][i])) i++; // prefix is the substring from the beginning to the last successfully checked i return words[0].substr(0, i); } console.log(1, prefix([])); console.log(2, prefix([""])); console.log(3, prefix(["abc"])); console.log(4, prefix(["abcdefgh", "abcde", "abe"])); console.log(5, prefix(["abc", "abc", "abc"])); console.log(6, prefix(["abc", "abcde", "xyz"]));Algunos de los problemas:
Su ciclo interno encontrará un return en su primera iteración. Esto significa que sus bucles nunca se repetirán y el valor devuelto siempre será un carácter.
Es incorrecto abordar strs[i+1] y strs[i+2] en su bucle, ya que esos índices se saldrán de los límites ( >= strs.length )
En lugar de realizar una comparación de carácter por carácter, puede usar la comparación de subcadena (prefijo) (en una operación): esto puede parecer un desperdicio, pero como dicha comparación ocurre "debajo" del código JavaScript, es muy rápido (y como el límite de tamaño de cadena es 200 caracteres, esto está bien).
El algoritmo podría comenzar seleccionando una cadena existente como prefijo y luego acortarla cada vez que haya una cadena en la entrada que no la tenga como prefijo. Al final te quedará el prefijo común.
Es bueno comenzar con la cadena más corta como candidato de prefijo inicial, ya que el prefijo común ciertamente no puede ser más largo que eso.
var longestCommonPrefix = function(strs) { let prefix = strs.reduce((acc, str) => str.length < acc.length ? str : acc); for (let str of strs) { while (str.slice(0, prefix.length) != prefix) { prefix = prefix.slice(0, -1); } } return prefix; }; let res = longestCommonPrefix(["flower","flow","flight"]); console.log(res);Un enfoque basado en la clasificación por longitud de palabra, y para la palabra más corta, para salir temprano, una validación y agregación de prefijos completamente basada en Array.every ...
function longestCommonPrefix(arr) { const charList = []; const [shortestWord, ...wordList] = // sort shallow copy by item `length` first. [...arr].sort((a, b) => a.length - b.length); shortestWord .split('') .every((char, idx) => { const isValidChar = wordList.every(word => word.charAt(idx) === char ); if (isValidChar) { charList.push(char); } return isValidChar; }); return charList.join(''); } console.log( longestCommonPrefix(["flower","flow","flight"]) ); .as-console-wrapper { min-height: 100%!important; top: 0; }