LeetCode: Prefix And Suffix Search Solution

1/**
2 * @param {string[]} words
3 */
4var WordFilter = function (words) {
5  this.mapPrefix = new Map()
6  this.mapSuffix = new Map()
7
8  for (const [wordIndex, word] of words.entries()) {
9    for (let i = 0; i <= word.length; i++) {
10      const [prefix, suffix] = [
11        word.substring(0, i),
12        word.substring(word.length - i),
13      ]
14
15      if (!this.mapPrefix.has(prefix)) {
16        this.mapPrefix.set(prefix, [])
17      }
18      if (!this.mapSuffix.has(suffix)) {
19        this.mapSuffix.set(suffix, [])
20      }
21
22      this.mapPrefix.get(prefix).push(wordIndex)
23      this.mapSuffix.get(suffix).push(wordIndex)
24    }
25  }
26}
27
28/**
29 * @param {string} prefix
30 * @param {string} suffix
31 * @return {number}
32 */
33WordFilter.prototype.f = function (prefix, suffix) {
34  if (!this.mapPrefix.has(prefix) || !this.mapSuffix.has(suffix)) {
35    return -1
36  }
37
38  const [prefixes, suffixes] = [
39    this.mapPrefix.get(prefix),
40    this.mapSuffix.get(suffix),
41  ]
42  let [i, j] = [prefixes.length - 1, suffixes.length - 1]
43
44  while (i >= 0 && j >= 0) {
45    if (prefixes[i] < suffixes[j]) {
46      j--
47    } else if (prefixes[i] > suffixes[j]) {
48      i--
49    } else {
50      return prefixes[i]
51    }
52  }
53
54  return -1
55}