1
\$\begingroup\$

The task

Given a string and a pattern, find the starting indices of all occurrences of the pattern in the string. For example, given the string "abracadabra" and the pattern "abr", you should return [0, 7].

My solution

function findStartingIndex(T, pattern) {
  let S = T;
  const res = [];
  while(true) {
    const i = S.indexOf(pattern);
    if (i === -1) { return res; }

    S = S.substring(i + 1);
    res.push(i ? i + 1 : i);
  }
  return res;
}
\$\endgroup\$

closed as off-topic by Graipher, Sᴀᴍ Onᴇᴌᴀ, IEatBagels, esote, pacmaninbw Jun 2 at 16:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Graipher, Sᴀᴍ Onᴇᴌᴀ, IEatBagels, esote, pacmaninbw
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ a challenge like this is much more instructive if you don't use indexOf. See also: Knuth-Morris-Pratt \$\endgroup\$ – Oh My Goodness May 31 at 1:32
  • \$\begingroup\$ @OhMyGoodness thanks, just skimmed through the article but it sounds interesting. Will reimplement the code \$\endgroup\$ – thadeuszlay May 31 at 1:35
  • \$\begingroup\$ Your code does not work for many inputs. \$\endgroup\$ – Blindman67 May 31 at 11:21
  • \$\begingroup\$ @Blindman67 yes, I didn't test it thoroughly. Just pushed the code. :( I wish I could delete this. \$\endgroup\$ – thadeuszlay May 31 at 11:35
  • \$\begingroup\$ @Blindman67 What is your opinion about this approach: codereview.stackexchange.com/questions/221409/… \$\endgroup\$ – thadeuszlay May 31 at 12:43
2
\$\begingroup\$

Your code contains a bug.

For banana and a, it should return [1, 3, 5], but it doesn't.

\$\endgroup\$
-1
\$\begingroup\$

Like @Roland Illig said, your code has bug with "banana" because of you mutable your string length each time you use your substring function.

I think you better replace your pattern each time it matchs by string that has same length pattern but does not match your pattern

function findStartingIndex(T, pattern) {
  let S = T;
  const res = [];
  while(true) {
    const i = S.indexOf(pattern);
    if (i === -1) { return res; }
    const newPattern = pattern.replace(/./,'_');

    S = S.replace(pattern, newPattern);
    res.push(i);
  }
  return res;
}

For string "banana" it will return [1,3,5]

Or you can consider my solution:

findStartingIndex = (s) => {
  const result = [];
  while (s.match(/abr/)) {
  result.push(s.match(/abr/).index);
  s=s.replace('abr','___');
  }
  return result;
}

Use regex here is not necessary but it is more flexible in case the pattern is dynamic.

Down voter: please consider your vote!

\$\endgroup\$
-1
\$\begingroup\$

Because I'm a fan of functional programming, I want to implement this without any for or while loops, which necessarily require mutating variables.

The way I'd do this, is with a recursive function.

function findIndexes(n, h, acc = [], currentIndex = 0) {
  const index = h.indexOf(n);

  if (index < 0) {
    return acc;
  } else {

    const newHaystack = h.slice(index + 1);
    return findIndexes(n, newHaystack, [...acc, index + currentIndex], currentIndex + index + 1);
  }
}

console.log(findIndexes("abr", "abracadabra"));
console.log(findIndexes("1", "1111"));
console.log(findIndexes("12", "121212"));
console.log(findIndexes("1212", "12121212")); //This one is a tricky case, as the sub strings overlap. 
console.log(findIndexes("1221", "1221221221"));
console.log(findIndexes("111", "11111111111"));
console.log(findIndexes("a", "banana"));

Now, whether you want to implement that indexOf function yourself is up to you, but in any case - this how I'd do the rest of it.

\$\endgroup\$
  • 2
    \$\begingroup\$ Any reason why this is being downvoted? \$\endgroup\$ – dwjohnston Jun 1 at 0:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.