Datos de muestra: Cadena: "barfoofoobarthefoobarman" Matriz de palabras: ["bar", "foo", "the"]
Salida: [6, 9, 12]
Me hicieron esta pregunta durante una entrevista. Debido a la limitación de tiempo, traté de encontrar todas las palabras posibles que se pudieran formar con la matriz de palabras (es decir, "barfoothe"), pero me dijeron que eso no sería escalable para matrices grandes. Se sugirió usar una estructura de datos de mapa, pero creo que mi solución tampoco escala, y es de fuerza bruta.
Aquí está la solución.
var solution = function(string, words) { let output = []; let wordsMap = new Map(); let wordsNumber = words.length; let wordLength = words[0].length; words.forEach((word) => { if (!wordsMap.has(word)) wordsMap.set(word, 1); else wordsMap.set(word, wordsMap.get(word) + 1); }); for (let i = 0; i <= string.length-(wordsNumber*wordLength); i+=wordLength) { let tempMap = new Map(wordsMap); let check = true; let tempString = string.substring(i, i + wordsNumber*wordLength); for (let j = 0; j <= tempString.length - wordLength; j += wordLength) { let tempString2 = tempString.substring(j, j + wordLength); if (tempMap.has(tempString2)) tempMap.set(tempString2, tempMap.get(tempString2) - 1); } for (let val of tempMap.values()){ if (val !== 0){ check = false break; } } if (check) output.push(i) } console.log(output); } solution("barfoothefoobarman", ["foo", "bar"]);¿Alguna sugerencia para una solución más inteligente?
Podría crear una expresión regular dinámica.
const words = ['foo', 'bar'] const rx = new RegExp(words.join('|'), 'g') // todo escape special charactersLuego busque lejos.
const counts = words.map(it=>0) // [0,0] // todo use map or object to track counts instead of array while (m = rx.exec(inputString)) { const index = words.indexOf(m[0]) counts[index]++ }Gracias por su pregunta. Creo que la pregunta en la entrevista fue menos sobre la solución correcta y más sobre el enfoque correcto.
La parte más complicada es encontrar las combinaciones de palabras. Hay varios enfoques aquí. Para mí es un caso claro de recursividad.
Así que mi enfoque sería:
Nota: uso indexOf() para el punto 2, pero creo que una coincidencia de expresiones regulares lo haría aún mejor porque encuentras todas las posibilidades de una palabra en una cadena y no solo la primera como con indexOf. Tendría sentido para cadenas más largas.
const arr = ["foo", "bar"]; const str = "barfoothefoobarman" let res = []; const combinations = (len, val, existing) => { if (len == 0) { res.push(val); return; } for(let i=0; i<arr.length; i++) { if(! existing[i]) { existing[i] = true; combinations(len-1, val + arr[i], existing); existing[i] = false; } } } const buildCombinations = (arr = []) => { for(let i = 0; i < arr.length; i++) { combinations(arr.length - i, "", []); } }; buildCombinations(arr); // exclude the base wordes from result array newRes = res.filter((e) => { if (! arr.includes(e)) { return e; } }) console.log('all word combinations:', newRes); // get the string position const _positions = []; newRes.forEach((w) => { let res = str.indexOf(w); if (res != -1 && ! _positions.includes(res)) { _positions.push(res); } }) // sort array and use Float64Array to speed up const positions = new Float64Array(_positions) console.log('positions', positions.sort())