preface

This article can not give you a good answer, can only put forward some guesses, because I do not have a good machine language foundation, have not read THE JS source code.

Source of problem

The source of the problem is a record of two submissions for a leetcode topic.

The only code difference between the two commits is to replace a for with indexOf.

The title

Given a string array of words, find the maximum length(word[I]) * length(word[j]) that contains no common letters. You can think of each word as containing only lowercase letters. If no such two words exist, return 0.

Example 1:

Input: [abcw ", "" baz", "foo", "bar", "XTFN", "abcdef"] output: 16 explanation: the two words "abcw", "XTFN".Copy the code

Example 2:

Input: [" a ", "ab", "ABC", "d", "CD" and "BCD", "abcd"] output: 4: this two word for "ab", the "CD".Copy the code

Example 3:

Input: [" A "," AA "," AAA "," aAAA "] Output: 0 Explanation: There are no such two words.Copy the code

Submit code

IndeOf not used:

var maxProduct = function (words) { const hasPublic = (x, y) => { for (let i = 0; i < x.length; i++) { for (let j = 0; j < y.length; j++) { if (x[i] === y[j]) return true } } return false } let max = 0 // let b = '' for (let i = 0; i < words.length; i++) { const e = words[i] for (let j = i; j < words.length; j++) { const ee = words[j] if (! hasPublic(e, ee)) { const m = e.length * ee.length max = max > m ? max : m } } } return max };Copy the code

Using indexOf:

var maxProduct = function (words) { const hasPublic = (x, y) => { for (let i = 0; i < x.length; i++) { if (y.indexOf(x[i]) > -1) { return true } } return false } let max = 0 for (let i = 0; i < words.length; i++) { const e = words[i] for (let j = i; j < words.length; j++) { const ee = words[j] if (! hasPublic(e, ee)) { const m = e.length * ee.length max = max > m ? max : m } } } return max };Copy the code

Some suspect that

After these two very different execution times, I guessed that the execution efficiency of indexOf was infinitely close to O(1).

Guess Cause 1

The internal JS implementation of indexOf is not implemented using JS, but is written in a lower-level language such as C, providing higher performance.

Guess Cause 2

JS may not use the circular way to obtain the string method like indexOf, and it is very likely to use the original, reverse and complement methods to achieve, but because the contents of the university have not been reviewed often, it is difficult to remember how to achieve, so I do not know whether it is feasible.

Some information retrieved from stackOverflow

Since there is no similar content found on the Intranet, I searched stackOverflow for you to check here.

indexOfIt doesn’t run in constant time

Test cases:

// create a very long string aaaa... ab... bc... cd (etc) let alpha = "abcdefghijklmnopqrstuvwxyz"; let s = Array.from(alpha, c => c.repeat(10000000)).join(""); // find each of the letters in this long string for (let c of alpha) { let start = performance.now(); s.indexOf(c); let end = performance.now(); console.log(end-start); }Copy the code

The last

If I’m lucky enough to find an answer to that question, I’ll come back to supplement this post.

If you know the answer, or have any other guesses, be sure to leave them in the comments section. Thanks a million.

Finally, I wish you all grow up together!