Estoy aprendiendo JavaScript y estaba trabajando en algunos problemas de DSA. Aquí está el que estoy tratando de resolver:
Escriba una función
isSubsequenceque tome dos cadenas y compruebe si los caracteres de la primera cadena forman una subsecuencia de los caracteres de la segunda cadena. En otras palabras, la función debe comprobar si los caracteres de la primera cadena aparecen en algún lugar de la segunda cadena, sin que cambie su orden.
isSubsequence('hello','hello world') //trueisSubsequence('sing','sting') //trueisSubsequence('abc','abracadabra') //trueisSubsequence('abc', 'acb') //false
Este es mi código:
const isSubsequence = (str1, str2) => { const createCharObj = (string) => { let outputObj = {}; for (let i = 0; i < string.length; i++) { if (outputObj[string[i]]) { outputObj[string[i]]++; } else { outputObj[string[i]] = 1; } } return outputObj; }; let charObj1 = createCharObj(str1); let charObj2 = createCharObj(str2); let compare = ""; for (let key in charObj2) { if (charObj2[key] < charObj1[key]) { return false; } else { let exceed = charObj1[key]; let i = 0; while (i < exceed) { compare += key; i++; } } } return compare === str1; }; console.log(isSubsequence("hello", "hello world")); console.log(isSubsequence("sing", "sting")); console.log(isSubsequence("abc", "abracadabra")); console.log(isSubsequence("abc", "acb"));Entiendo que mi solución no es eficiente, pero creo que la lógica es adecuada.
Sin embargo, cuando lo ejecuto en un IDE de Udemy, aparece un error que dice:
se esperaba que lo falso fuera verdadero
Sin embargo, cuando lo ejecuté en el código VS, no hubo ningún problema. Por favor, hágame saber dónde cometí el error.
Su algoritmo no es correcto. El sitio de desafío de código (Udemy) también está alimentando su código con otras entradas, y para algunas de ellas (no las que enumeró) su código arroja un resultado incorrecto.
Asume que si una letra en la segunda cadena corresponde a una letra en la primera cadena, esa debe ser la que también está en la secuencia correcta. Esto no es necesariamente cierto la primera vez que se encuentra este carácter en la segunda cadena.
Por ejemplo, su código devolverá el resultado incorrecto para esta entrada:
console.log(isSubsequence("abc", "acabc"));Esto se debe a que en la segunda cadena, la primera aparición de "c" está antes de la primera aparición de "b", pero debería haber ignorado esa primera "c".
Sugerencias:
La iteración principal debe estar sobre la primera cadena, no sobre la segunda.
Una vez que se encuentra un carácter de la primera cadena en la segunda cadena, todos los caracteres que preceden a ese carácter en la segunda cadena deben ignorarse por completo en cualquier búsqueda siguiente.
Solución de spoiler:
const isSubsequence = (str1, str2) => { let j = -1; for (let ch of str1) { j = str2.indexOf(ch, j + 1); if (j === -1) return false; } return true; };