1032.字符流.md

1032.字符流

/*
 * @lc app=leetcode.cn id=1032 lang=typescript
 *
 * [1032] 字符流
 */

// @lc code=start

class StreamChecker {
  constructor(words: string[]) {}

  query(letter: string): boolean {}
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */
// @lc code=end

解法 1: Trie

class StreamChecker {
  root: { [ch: string]: any } = {}
  s = ''
  constructor(words: string[]) {
    for (const word of words) {
      let node = this.root
      for (let i = word.length - 1; i >= 0; i--) {
        const ch = word[i]
        if (!node[ch]) node[ch] = {}
        node = node[ch]
      }
      node.done = true
    }
  }

  query(letter: string): boolean {
    this.s += letter
    let node = this.root
    for (let i = this.s.length - 1; i >= 0; i--) {
      const ch = this.s[i]
      node = node[ch]
      if (!node) break
      if (node.done) return true
    }
    return false
  }
}

Case

test.each([
  {
    input: {
      ops: [
        'StreamChecker',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
        'query',
      ],
      params: [[['cd', 'f', 'kl']], ['a'], ['b'], ['c'], ['d'], ['e'], ['f'], ['g'], ['h'], ['i'], ['j'], ['k'], ['l']],
    },
    output: [null, false, false, false, true, false, true, false, false, false, false, false, true],
  },
])('input: param = $input.param', ({ input: { ops, params }, output }) => {
  const cls = new StreamChecker(...params[0])
  const res: (boolean | null)[] = [null]
  for (let i = 1; i < ops.length; i++) {
    res[i] = cls[ops[i]](...params[i])
  }
  expect(res).toEqual(output)
})