745.前缀和后缀搜索.md

745.前缀和后缀搜索

/*
 * @lc app=leetcode.cn id=745 lang=typescript
 *
 * [745] 前缀和后缀搜索
 */

// @lc code=start
class WordFilter {
  constructor(words: string[]) {}

  f(pref: string, suff: string): number {}
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */
// @lc code=end

解法 1: 预处理前后缀

我们可以把所有可能的前后缀组合都预处理出来放到哈希表中,查询只要看哈希表中是否存在想要查询的前后缀组合即可.

设 $n=words.length,m=wors[i].length$,则预处理的时间复杂度为 $O(nm^2)$,最多为 $4.910^5$,每次查询的复杂度为 $O(1)$,最多会查询 $q=10^4$ 次,总的时间复杂度为 $n*m^2+q$

class WordFilter {
  private map = new Map<string, number>()
  constructor(words: string[]) {
    const { map } = this
    for (let [i, word] of words.entries()) {
      for (let j = 0; j < word.length; j++) {
        const pre = word.slice(0, j + 1)
        for (let k = 0; k < word.length; k++) {
          const key = pre + ',' + word.slice(k)
          map.set(key, Math.max(map.get(key) ?? 0, i))
        }
      }
    }
  }

  f(pref: string, suff: string): number {
    return this.map.get(pref + ',' + suff) ?? -1
  }
}

Case

test.each([{ input: { ops: ['WordFilter', 'f'], params: [[['apple']], ['a', 'e']] }, output: [null, 0] }])(
  'input: param = $input.param',
  ({ input: { ops, params }, output }) => {
    const cls = new WordFilter(...(params[0] as [string[]]))
    const res: (number | null)[] = [null]
    for (let i = 1; i < ops.length; i++) {
      res[i] = cls[ops[i] as 'f'](...(params[i] as [string, string]))
    }
    expect(res).toEqual(output)
  },
)