Number of Matching Subsequences

Description

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

Solution(javascript)

/** 暴力解法 O(m*n)
 * @param {string} S
 * @param {string[]} words
 * @return {number}
 */
// const numMatchingSubseq = function (S, words) {
//   const isSubsequence = (word) => {
//     let index = 0
//     for (let i = 0; i < S.length; i++) {
//       if (S[i] === word[index]) {
//         index += 1
//         if (index >= word.length) {
//           return true
//         }
//       }
//     }
//     return false
//   }
//   return words.reduce((acc, word) => {
//     if (isSubsequence(word)) {
//       return acc + 1
//     }
//     return acc
//   }, 0)
// }

// https://leetcode.com/problems/number-of-matching-subsequences/discuss/117634/Efficient-and-simple-go-through-words-in-parallel-with-explanation
// 一轮遍历解决，记录每个 word 下一次需要的字母
const numMatchingSubseq = function (S, words) {
  const map = words.reduce((acc, word, index) => {
    const c = word[0]
    acc[c] = acc[c] || []
    acc[c].push([index, 0])
    return acc
  }, {})
  let num = 0
  for (let i = 0; i < S.length; i++) {
    if (map[S[i]] !== undefined) {
      const list = map[S[i]]
      map[S[i]] = undefined
      // eslint-disable-next-line no-loop-func
      list.forEach(([wordIndex, charIndex]) => {
        if (charIndex === words[wordIndex].length - 1) {
          num += 1
        } else {
          const nextChar = words[wordIndex][charIndex + 1]
          map[nextChar] = map[nextChar] || []
          map[nextChar].push([wordIndex, charIndex + 1])
        }
      })
    }
  }
  return num
}