792.匹配子序列的单词数.md

792.匹配子序列的单词数

/*
 * @lc app=leetcode.cn id=792 lang=typescript
 *
 * [792] 匹配子序列的单词数
 */

// @lc code=start
function numMatchingSubseq(s: string, words: string[]): number {}
// @lc code=end

解法 1: 预处理前缀位置

function numMatchingSubseq(s: string, words: string[]): number {
  const n = s.length
  const p: number[][] = new Array(n),
    cur = new Array(26).fill(-1)
  for (let i = 0; i < n; i++) {
    p[i] = [...cur]
    const j = s.charCodeAt(i) - 97
    cur[j] = i
  }
  let res = 0
  next: for (let word of words) {
    let x = -1
    for (let i = word.length - 1; i >= 0; i--) {
      const j = word.charCodeAt(i) - 97
      if (x === -1) {
        x = cur[j]
      } else {
        x = p[x][j]
      }
      if (x === -1) continue next
    }
    res++
  }
  return res
}

Case

test.each([
  { input: { s: 'abcde', words: ['a', 'bb', 'acd', 'ace'] }, output: 3 },
  { input: { s: 'dsahjpjauf', words: ['ahjpjau', 'ja', 'ahbwzgqnuk', 'tnmlanowax'] }, output: 2 },
])('input: s = $input.s, words = $input.words', ({ input: { s, words }, output }) => {
  expect(numMatchingSubseq(s, words)).toEqual(output)
})