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\$
  • 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 '19 at 1:32
  • \$\begingroup\$ @OhMyGoodness thanks, just skimmed through the article but it sounds interesting. Will reimplement the code \$\endgroup\$ – thadeuszlay May 31 '19 at 1:35
  • \$\begingroup\$ Your code does not work for many inputs. \$\endgroup\$ – Blindman67 May 31 '19 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 '19 at 11:35
  • \$\begingroup\$ @Blindman67 What is your opinion about this approach: codereview.stackexchange.com/questions/221409/… \$\endgroup\$ – thadeuszlay May 31 '19 at 12:43
2
\$\begingroup\$

Your code contains a bug.

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

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

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

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