README.md

792. Number of Matching Subsequences

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

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

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solutions (Rust)

1. Solution

impl Solution {
    pub fn num_matching_subseq(s: String, words: Vec<String>) -> i32 {
        let mut indices = vec![vec![]; 26];
        let mut ret = 0;

        for (i, c) in s.bytes().enumerate() {
            indices[(c - b'a') as usize].push(i);
        }

        for word in &words {
            let mut i = 0;
            let mut flag = true;

            for c in word.bytes() {
                match indices[(c - b'a') as usize].binary_search(&i) {
                    Err(j) if j == indices[(c - b'a') as usize].len() => {
                        flag = false;
                        break;
                    }
                    Ok(j) | Err(j) => i = indices[(c - b'a') as usize][j] + 1,
                }
            }

            ret += flag as i32;
        }

        ret
    }
}