How to find a substring in a string?

Help correctly solve a task with CodeWars.
The text of the task in English.
Given an array of words and a compound word target, 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]]


Actually, the problem was solved several times, but all attempts are reduced to a bust cycle in the cycle, and such a condition does not pass the time limit with a huge array. But how to solve it faster I'll never know.
compoundMatch function(words, target) { /*given an array of words and the second argument is a word that consists of two from an array, you need to find out what is and return them */
 const arr = [];
 for (let i = 0; i < words.length; i++) {
 if (target.includes(words[i])) { // here find the substrings that are in the second argument
 arr.push(words[i]); // put them in array
}
}
 let part1;
 let part2;
 outer: for (let i = 0; i < arr.length; i++) { // iterate the array of substrings
 if (target.includes(arr[i])) { 
 part1 = arr[i]; // find the part of the word
 for (let j = 0; j < arr.length; j++) { /* here it is, as I understand it, spent most of the time, and these cycles need to get rid of*/
 if (target.replace(part1, ") === arr[j]) { // take it from the word, and if the remainder is equal to the element from the array
 part2 = arr[j]; // save it
 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'); // need to return like this ['super', 'bowl', [0, 2]]

I suspect that this approach is generally not good for solving problems with large arrays, but otherwise do not understand, prompt at least in what side to dig, or direct in the right direction. Maybe someone has already solved this problem, could you tell me the options. Thanks in advance.
March 23rd 20 at 19:25
3 answers
March 23rd 20 at 19:27
Solution
and subscribe myself dig deeper, I wrote "head" with an attached loop and does not pass in time

compoundMatch function(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
}
An elegant solution, it would be necessary to remember. - Terrill.Stiedemann79 commented on March 23rd 20 at 19:30
@Terrill.Stiedemann79, but garbage doesn't pass the same ;D - dayana commented on March 23rd 20 at 19:33
@dayana, well, that is another question)) the main thing that is beautiful)) - Terrill.Stiedemann79 commented on March 23rd 20 at 19:36
@Terrill.Stiedemann79, shorter from discussions on their forum, so the catch is that the array a lot of duplicates, and must ignore

tried to withdraw the words.length, so there is one test 10000335 of elements in the array is nested loop on any fast to count :D

but kata is just a roundabout, there's a pretty obvious decision, most likely - dayana commented on March 23rd 20 at 19:39
@dayana, yeah, I'm here today 4 hours spent on the solution, and the tests looking, there are random tests and up to 100000 array is created, and of course such an array in a loop to iterate over it to put it mildly is not rational, but damn, other than brute force another solution is not found... - Terrill.Stiedemann79 commented on March 23rd 20 at 19:42
@Terrill.Stiedemann79, that pass 247 test of the 300, now the weak point is probably the indexOf, which again runs through the array hmmm

compoundMatch function(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, [round, i]]
}

}

 return null
}
- dayana commented on March 23rd 20 at 19:45
@dayana, wow, it looks like a working version, test again, time does not pass, or something else? - Terrill.Stiedemann79 commented on March 23rd 20 at 19:48
@Terrill.Stiedemann79, ahahaha, took everything in the object, and searching for the key of the object instead of an array, because we need to retain ONLY the FIRST word of all the duplicates

compoundMatch function(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
}


meanwhile in other people's decisions lol

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
- dayana commented on March 23rd 20 at 19:51
@dayana, damn, that's thought about the object... but not smart enough... Cool, thanks for the help! me now to celebrate this decision? - Terrill.Stiedemann79 commented on March 23rd 20 at 19:54
@Terrill.Stiedemann79, Yes pofik :) - dayana commented on March 23rd 20 at 19:57
March 23rd 20 at 19:29
Solution
Decided clumsy, time passes. But there are cool solutions short in the top!

To circumvent the array of words once is enough.
The next word may be in target in the zero position, then it is "first", or to another, then it is necessary to check that the position + the length of the words to accurately get to the end target.
Fold in the arrays, the position of the matching word and the length of the desired other words.
Found ocherednoe Initial word - look, whether he has ACC. the required length was found among the Finite.
Found another Final word - see if there are corresponding at the desired length of the Initial among the already found.
Once found a pair, the returned answer.

my so currently the solution
fn function(words, target) {

 const length = words.length, targetLength = target.length;

 const aWord = []; // indexes of words in aWords
 const aWant = []; // how long is not enough to a whole

 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) { // at the beginning of a compound, the first Podkowa

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 { // not the beginning of a word was found, the second word, the end goal

 if (x + wordLength !== targetLength) continue; // does not get in the end

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;
}
cool idea in the top

Beat the target word across all the possible options for couples - and they are even less than the length of the target word.
Look for every two words in the given array. If both were found, here it is, the solution.
In 8 lines. If preload formatting-6.
cool it in the solution to check for -1 because only ~(-1) = 0
if (~i1 && ~i2) - dayana commented on March 23rd 20 at 19:32
@dayana, too, sometimes use such a short record:
if (!!~str.indexOf(search)) {
 // found
}
- troy_Barrows commented on March 23rd 20 at 19:35
March 23rd 20 at 19:31
Solution
and not too short. but during the fit.
compoundMatch function(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;
}

Find more questions by tags JavaScript