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

Question

[Саша Ящук]

Помогите правильно решить задачу с 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]]

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

Comments

[Lynn «Кофеман»]

Ссылка не открывается

[Саша Ящук]

Алексей Тен, https://www.codewars.com/kata/5aaae0f5fd8c069e8c00016e сори, так должна

[Максим Толкачев]

Слова в массиве могут повторятся, если отбросить их, то цикл нахождения пары - будет занимать мизерное время, по сравнению с циклом определения, какие вообще слова могут быть составлять целевое слово.
Цель всегда состоит из двух слов, поэтому для первого слова совпадает первая буква, а для второго - последняя.
Дальше не подскажу (думаю этого должно быть достаточно) - но я решил эту задачу

[Роман]

Саша Ящук, а в какое время нужно уложится? и где его посмотреть?

Answer 1

[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
}

Comments

[Саша Ящук]

Элегантное решение, надо бы запомнить.

[hzzzzl]

Саша Ящук, да фигня, тоже не проходит же ;Д

[Саша Ящук]

hzzzzl, ну так это уже другой вопрос)) главное что красиво))

[hzzzzl]

Саша Ящук, короче судя по обсуждениям на их форуме, так загвоздка в том, что в массиве много дубликатов, и их надо игнорить

попробовал выводить words.length, так там в одном тесте 10000335 элементов в массиве, такое вложенным циклом по любому быстро не посчитать :D

но ката всего на пятерочку, где-то есть довольно очевидное решение, скорее всего

[Саша Ящук]

hzzzzl, да, я вот сегодня часа 4 потратил на решение, уже и тесты их смотрел, там random тесты и до 100000 массив создают, и конечно такой массив еще в цикле перебирать это мягко говоря не рационально, но блин, кроме как перебора другого решения не нашел...

[hzzzzl]

Саша Ящук, вот прохожу 247 тестов из 300, сейчас слабое место это наверно indexOf, которое еще раз пробегает по массиву хммм

function compoundMatch(w, t) {

  for (let i = 0; i < w.length; i++) {
  
    const w1 = w[i]

    if(t.startsWith(w1)) {
      const w2 = t.replace(w1, '')
      const found = w.indexOf(w2)
      if(found !== -1) return [w1, w2, [i, found]]
    }

    if(t.endsWith(w1)) {
      const w2 = t.replace(w1, '')
      const found = w.indexOf(w2)
      if(found !== -1) return [w1, w2, [found, i]]
    }

  }
  
  return null
}

[Саша Ящук]

hzzzzl, круто, классное решение, выглядит как вполне рабочий вариант, тесты опять по времени не проходят, или что то другое?

[hzzzzl]

Саша Ящук, ааахаха, зафигачил всё в объект, и ищу по ключам объекта, вместо массива, потому что нам надо сохранять ТОЛЬКО ПЕРВОЕ слово из всех дубликатов

function compoundMatch(w, t) {

  const dict = {}
  
  for (let i = 0; i < w.length; i++) {
    if(dict[w[i]] === undefined) dict[w[i]] = i
  }

  for (const key in dict) {
  
    if(t.startsWith(key)) {
      const w2 = t.replace(key, '')
      const found = dict[w2]
      if(found) return [key, w2, [dict[key], found]]
    }

    if(t.endsWith(key)) {
      const w2 = t.replace(key, '')
      const found = dict[w2]
      if(found) return [key, w2, [found, dict[key]]]
    }
    
  }
  
  return null
}

тем временем в чужих решениях лол

compoundMatch=(S,Q,M)=>~(S.forEach((V,F)=>M[V]=F,M={}),V=S.findIndex(V=>V==Q.slice(0,V.length)&&null!=(B=M[Q.slice(V.length)])))?V<B?[S[V],S[B],[V,B]]:[S[B],S[V],[V,B]]:null

[Саша Ящук]

hzzzzl, блин, вот думал об объекте... но не додумал... Круто, спасибо за помощь! ка мне теперь отметить это решением?

[hzzzzl]

Саша Ящук, да пофик :)

Answer 2

[Сергей Соколов]

Решил топорно, по времени проходит. Но там такие крутые решения короткие в топе!

Обходить массив слов достаточно один раз.
Очередное слово может найтись в 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.

Comments

[hzzzzl]

прикольно он в том решении проверяет на -1, потому что только ~(-1) = 0
if (~i1 && ~i2)

[Сергей Соколов]

hzzzzl, тоже иногда пользуюсь такой короткой записью:

if (!!~str.indexOf(search)) {
  // найдена
}

Answer 3

[Роман]

тоже решил и тоже не коротко. но во время укладывается.

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;
}