宫水三叶的刷题日记

V1

2022/11/17阅读:13主题:全栈蓝

792. 匹配子序列的单词数 : 常规预处理优化匹配过程

题目描述

这是 LeetCode 上的 792. 匹配子序列的单词数 ,难度为 中等

Tag : 「二分」、「哈希表」

给定字符串 s 和字符串数组 words, 返回  words[i] 中是 s 的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是""),而不改变其余字符的相对顺序。

例如, “ace”“abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]

输出: 3

解释: 有三个是 s 的子序列的单词: "a""acd""ace"

示例 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

输出: 2

提示:

  • words[i]s 都只由小写字母组成。

预处理 + 哈希表 + 二分

朴素判定某个字符串是为另一字符串的子序列的复杂度为 ,对于本题共有 个字符串需要判定,每个字符串最多长为 ,因此整体计算量为 ,会超时。

不可避免的是,我们要对每个 进行检查,因此优化的思路可放在如何优化单个 的判定操作。

朴素的判定过程需要使用双指针扫描两个字符串,其中对于原串的扫描,会有大量的字符会被跳过(无效匹配),即只有两指针对应的字符相同时,匹配串指针才会后移。

我们考虑如何优化这部分无效匹配。

对于任意一个 而言,假设我们当前匹配到 位置,此时我们已经明确下一个待匹配的字符为 ,因此我们可以直接在 s 中字符为 的位置中找候选。

具体的,我们可以使用哈希表 maps 进行预处理:以字符 为哈希表的 key,对应的下标 集合为 value,由于我们从前往后处理 s 进行预处理,因此对于所有的 value 均满足递增性质。

举个 🌰 : 对于 s = abcabc 而言,预处理的哈希表为 {a=[0,3], b=[1,4], c=[2,5]}

最后考虑如何判定某个 是否满足要求:待匹配字符串 w 长度为 m,我们从前往后对 w 进行判定,假设当前判待匹配位置为 ,我们使用变量 idx 代表能够满足匹配 的最小下标(贪心思路)。

对于匹配的 字符,可以等价为在 map[w[i]] 中找到第一个大于 idx 的下标,含义在原串 s 中找到字符为 w[i] 且下标大于 idx 的最小值,由于我们所有的 map[X] 均满足单调递增,该过程可使用「二分」进行。

Java 代码:

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int n = s.length(), ans = 0;
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault(s.charAt(i), new ArrayList<>());
            list.add(i);
            map.put(s.charAt(i), list);
        }
        for (String w : words) {
            boolean ok = true;
            int m = w.length(), idx = -1;
            for (int i = 0; i < m && ok; i++) {
                List<Integer> list = map.getOrDefault(w.charAt(i), new ArrayList<>());
                int l = 0, r = list.size() - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (list.get(mid) > idx) r = mid;
                    else l = mid + 1;
                }
                if (r < 0 || list.get(r) <= idx) ok = false;
                else idx = list.get(r);
            }
            if (ok) ans++;
        }
        return ans;
    }
}

TypeScript 代码:

function numMatchingSubseq(s: string, words: string[]): number {
    let n = s.length, ans = 0
    const map = new Map<StringArray<number>>()
    for (let i = 0; i < n; i++) {
        if (!map.has(s[i])) map.set(s[i], new Array<number>())
        map.get(s[i]).push(i)
    }
    for (const w of words) {
        let ok = true
        let m = w.length, idx = -1
        for (let i = 0; i < m && ok; i++) {
            if (!map.has(w[i])) {
                ok = false
            } else {
                const list = map.get(w[i])
                let l = 0, r = list.length - 1
                while (l < r) {
                    const mid = l + r >> 1
                    if (list[mid] > idx) r = mid
                    else l = mid + 1
                }
                if (r < 0 || list[r] <= idx) ok = false
                else idx = list[r]
            }
        }
        if (ok) ans++
    }
    return ans
}

Python3 代码:

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        dmap = defaultdict(list)
        for i, c in enumerate(s):
            dmap[c].append(i)
        ans = 0
        for w in words:
            ok = True
            idx = -1
            for i in range(len(w)):
                idxs = dmap[w[i]]
                l, r = 0, len(idxs) - 1
                while l < r :
                    mid = l + r >> 1
                    if dmap[w[i]][mid] > idx:
                        r = mid
                    else:
                        l = mid + 1
                if r < 0 or dmap[w[i]][r] <= idx:
                    ok = False
                    break
                else:
                    idx = dmap[w[i]][r]
            ans += 1 if ok else 0
        return ans
  • 时间复杂度:令 ns 长度,mwords 长度,l = 50 长度的最大值。构造 map 的复杂度为 ;统计符合要求的 的数量复杂度为 。整体复杂度为
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.792 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1