Как быстро найти подстроку в строке?

Помогите правильно решить задачу с CodeWars.
Текст задачи на англ.
Given an array of words and a target compound word, your objective is to find the two words which combine into the target word, returning both words in the order they appear in the array, and their respective indices in the order they combine to form the target word. Words in the array you are given may repeat, but there will only be one unique pair that makes the target compound word. If there is no match found, return null/nil/None.

Note: Some arrays will be very long and may include duplicates, so keep an eye on efficiency.

Examples:
fn(['super','bow','bowl','tar','get','book','let'], "superbowl")      =>   ['super','bowl',   [0,2]]
fn(['bow','crystal','organic','ally','rain','line'], "crystalline")   =>   ['crystal','line', [1,5]]
fn(['bow','crystal','organic','ally','rain','line'], "rainbow")       =>   ['bow','rain',     [4,0]]
fn(['bow','crystal','organic','ally','rain','line'], "organically")   =>   ['organic','ally', [2,3]]
fn(['top','main','tree','ally','fin','line'], "mainline")             =>   ['main','line',    [1,5]]
fn(['top','main','tree','ally','fin','line'], "treetop")              =>   ['top','tree',     [2,0]]


Собственно, задачу решил уже несколько раз, но все попытки сводятся к перебору цикла в цикле, и такое условие не проходит по ограничению по времени при огромных массивах. Но как решить ее быстрее ума не приложу.
function compoundMatch(words, target) { /*дан массив слов и вторым аргументом слово, которое состоит из двух из массива, нужно найти из каких слов состоит и вернуть их */
  const arr = [];
  for (let i = 0; i < words.length; i++) {
    if (target.includes(words[i])) { // здесь нахожу подстроки, которые имеются в во втором аргументе
      arr.push(words[i]); // складываю их в массив
    }
  }
  let part1;
  let part2;
  outer: for (let i = 0; i < arr.length; i++) { // перебираю массив подстрок
    if (target.includes(arr[i])) { 
      part1 = arr[i]; // нахожу часть слова
      for (let j = 0; j < arr.length; j++) { /* вот на это, как я понимаю, тратится бОльшая часть времени и от этих циклов надо избавляться*/
        if (target.replace(part1, '') === arr[j]) { // отнимаю ее от слова и если оставшаяся часть равна элементу из массива
          part2 = arr[j]; // сохраняю ее
          break outer;
        }
      }
    }
  }
  if (part1 === undefined || part2 === undefined) {
    return null;
    }
  let indexes = part1 + part2 === target ? [words.indexOf(part1), words.indexOf(part2)] : [words.indexOf(part2), words.indexOf(part1)];
  console.log([part1, part2, indexes]);
}


compoundMatch(['super','bow','bowl','tar','get','book','let'], 'superbowl'); // вернуть нужно в таком виде ['super', 'bowl', [0, 2]]

Я подозреваю, что этот подход в целом не годится для решения задач с крупными массивами, но как иначе сделать не понимаю, подскажите хотя бы в какую сторону копать, или направьте в правильное русло. Может быть кто то уже решал эту задачу, подскажите варианты. Заранее спасибо.
  • Вопрос задан
  • 886 просмотров
Решения вопроса 3
hzzzzl
@hzzzzl
а подпишусь и сам поковыряю, навскидку написал "в лоб" с вложенным циклом и тоже не проходит по времени

function compoundMatch(words, target) {
  for (let i = 0; i < words.length; i++) {

    for (let ii = 0; ii < words.length; ii++) {
      const m1 = words[i] + words[ii] === target
      const m2 = words[ii] + words[i] === target

      if (i !== ii && (m1 || m2)) {
        const arr = m1 ? [i, ii] : [ii, i]
        return [words[i], words[ii], arr]
      }
    }

  }
  
  return null
}
Ответ написан
sergiks
@sergiks Куратор тега JavaScript
♬♬
Решил топорно, по времени проходит. Но там такие крутые решения короткие в топе!

Обходить массив слов достаточно один раз.
Очередное слово может найтись в target в нулевой позиции - тогда оно "первое", или в другой, тогда надо проверить что та позиция + длина слова точно достают до конца target.
Складывать в массивы позицию подходящего слова и длину искомого другого слова.
Нашли очереденое Начальное слово - смотрим, есть ли ему соотв. искомая длина среди найденных Конечных.
Нашли очередное Конечное слово - смотрим, есть ли соответствующее ему по искомой длине Начальное среди уже найденных.
Как только нашлась пара - возвращаем ответ.

мое так-себе решение
function fn(words, target) {
  
  const length = words.length, targetLength = target.length;
  
  const aWord = [];   // индексы слов в aWords
  const aWant = [];   // какой длины не хватает до целого
  
  const bWord = [];
  const bWant = [];


  for (let i = 0; i < length; i++) {

    const word = words[i];

    const x = target.indexOf(word);
    if (-1 === x) continue;
    
    const wordLength = word.length;
    const want = targetLength - wordLength;

    if (x === 0) { // в начале составного, первое подслово
      
      aWord.push(i);
      aWant.push(want);
      
      const bIndex = bWant.indexOf(wordLength);
      if (-1 === bIndex) continue;
      
      const bWordIndex = bWord[bIndex];
      return [words[bWordIndex], word, [i, bWordIndex]];
      
    } else { // не в начале слова встретилось - второе слово, в конце цели
      
      if (x + wordLength !== targetLength) continue; // не попадает в конец
      
      bWord.push(i);
      bWant.push(want);
      
      const aIndex = aWant.indexOf(wordLength);
      
      if (-1 === aIndex) continue;
      const aWordIndex = aWord[aIndex];
      return [words[aWordIndex], word, [aWordIndex, i]];

    }
  }
  
  return null;
}
крутая идея в топе

Бить целевое слово во всех возможных вариантах пар - а их даже меньше, чем длина целевого слова!
Искать каждые два слова в данном массиве. Если оба нашлись, вот оно, решение.
В 8 строк. Если поджать форматирование, то в 6.
Ответ написан
lastuniverse
@lastuniverse
Всегда вокруг да около IT тем
тоже решил и тоже не коротко. но во время укладывается.
function compoundMatch(words, target) {
  let srclist = {};
  let list = words.reduce((a,w,i)=>{
    if( srclist[w] ) return a;
    srclist[w] = { w:w, i:i };
    if( target.indexOf(w) !== 0 ) return a;
    a[w] = { w:w, i:i };
    return a;
  },{});
  
  srclist = Object.values(srclist);
  list = Object.values(list);
  const l = Object.keys(srclist).le

  for(var i=0; i<list.length; i++){
    const left = list[i];  
    left.s = target.substring(left.w.length);
    for(var j=0; j<srclist.length; j++){
      const right = srclist[j];
      if( right.w.length === left.s.length && right.w === left.s )
        return ( left.i<right.i ? [left.w, right.w, [left.i, right.i]] : [right.w, left.w, [left.i, right.i]] );
    }
  }
  return null;
}
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы