0
\$\begingroup\$

I was wondering how efficient my code is creating custom indexOf for strings in JavaScript using regex instead of looping with a for statement the whole way in most solution I find and I believe this got \$O(1)\$ since no loop is needed.

The idea is to use regex that put either the key or any list of word that is not key; this way I know that the value will be either in arr[0] or arr[1]. I also check using regex earlier whether the key exist in the value or not; this way I created non-looping indexOf with regex. This way I just return 0 if the key is in arr[0] or arr[0].length if it not in arr[0].

function findindex(value,key){
  let regex = RegExp( "((?!"+key+").)+|"+key , "ig" ); //regex for separating keys in the array
  let regex2 = RegExp(key,"ig");  // regex for checking if the key is exist in the value or not

  //first check before looping whether key is available in array or not
  if( !regex2.test(value) || value.length < key.length ){
    return -1;
  }

  let arr  = value.match(regex); //make an array  

  //alternative with condition statement
  return ( arr[0] === key || regex2.test(arr[0]) ) ? 0 : arr[0].length; 
}
\$\endgroup\$
2
\$\begingroup\$

Too sad, it's not O(1). There is a cost for:

  • Constructing the regex into a DFA
  • Calling test() or match() on the regex for the value

Complexities:

  • A well implemented regex construction will be O(M) where M is the length of the key.
  • While test/matching it afterwards will be O(N) where N is the length of the value. (best case, e.g. regexes with backtracking can result in horrible complexities)

So a couple of improvements can be:

  • if the key is always the same. Construct the regex for the key only once.
  • first start with comparing the length of the value and key before calling the more expensive test()-match() methods.
  • apart from that, the idea of a regex is ok but I don't know if it's the most understandable way of writing an indexOf.

  • Reference: Regex Complexities on SO

\$\endgroup\$
2
  • \$\begingroup\$ I do agree that this not a really understandable way of writing indexOf, just though I could make it faster by reducing the loop. As I just learned regex I though it's a cheap way to avoid looping to get a value. never thought calling test() and match() is really expensive. thanks a lot for the suggestion \$\endgroup\$ Dec 13 '18 at 10:24
  • \$\begingroup\$ I wouldn't say "really expensive", in general it will be quite similar to a normal loop. And far better than a naïve implementation using 2 loops with worst case O(NM). You can have a look at some popular string search algorithms like "Rabin-Karp", "Boyer-Moore" or my favourite "Knuth-Morris-Pratt" that is construction a DFA and using it which can give you more insights in this topic. \$\endgroup\$
    – Sam Segers
    Dec 13 '18 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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