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

Categories:

题目描述
思路分析
1. 解法一：位置索引 + 二分（推荐）
相似题目

题目描述

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

思路分析

解法一：位置索引 + 二分（推荐）

核心思路：

预处理原串每个字符的出现位置列表。

对每个单词，逐字符二分查找下一位置。

若所有字符都能找到递增位置，则为匹配子序列。

复杂度分析：

时间复杂度：O((n + total) log n)。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<>();
        }
        for (int i = 0; i < s.length(); i++) {
            pos[s.charAt(i) - 'a'].add(i);
        }

        int res = 0;
        for (String word : words) {
            if (isSubseq(word, pos)) {
                res++;
            }
        }

        return res;
    }

    private boolean isSubseq(String word, List<Integer>[] pos) {
        int prev = -1;
        for (int i = 0; i < word.length(); i++) {
            List<Integer> list = pos[word.charAt(i) - 'a'];
            int idx = upperBound(list, prev);
            if (idx == list.size()) {
                return false;
            }
            prev = list.get(idx);
        }
        return true;
    }

    private int upperBound(List<Integer> list, int target) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

func numMatchingSubseq(s string, words []string) int {
	pos := make([][]int, 26)
	for i := 0; i < len(s); i++ {
		pos[s[i]-'a'] = append(pos[s[i]-'a'], i)
	}

	res := 0
	for _, word := range words {
		if isSubseq(word, pos) {
			res++
		}
	}

	return res
}

func isSubseq(word string, pos [][]int) bool {
	prev := -1
	for i := 0; i < len(word); i++ {
		list := pos[word[i]-'a']
		idx := upperBound(list, prev)
		if idx == len(list) {
			return false
		}
		prev = list[idx]
	}
	return true
}

func upperBound(list []int, target int) int {
	left, right := 0, len(list)
	for left < right {
		mid := left + (right-left)/2
		if list[mid] <= target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

相似题目

题目	难度	考察点
392. 判断子序列	简单	双指针
524. 通过删除字母匹配到字典里最长单词	中等	双指针
522. 最长特殊序列 II	中等	子序列
115. 不同的子序列	困难	动态规划
1143. 最长公共子序列	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/20717607