LeetCode_多指针_二分搜索_中等_792.匹配子序列的单词数
1.题目
给定字符串 s 和字符串数组 words, 返回 words[i] 中是 s 的子序列的单词个数。
字符串的子序列是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是 none),而不改变其余字符的相对顺序。
例如, “ace” 是 “abcde” 的子序列。
示例 1:
输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。
示例 2:
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2
提示:
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-matching-subsequences
2.思路
(1)直接判断子序列
如果直接判断数组 words 中的每个 word 是否为 s 的子序列,其判断方法可参考LeetCode_双指针_二分搜索_简单_392.判断子序列这篇文章,该文章中提供了双指针法和二分搜索法来进行判断。但是使用双指针法在 LeetCode 中提交时会出现“超出时间限制”的提示!
(2)多指针
思路参考本题官方题解。
双指针法中是每一个单词分别和字符串 s 进行匹配,这样对于每一次匹配都需要从头开始遍历字符串 s,这增加了额外的时间开销。所以我们考虑将字符串数组 words 中的全部字符串和字符串 s 同时进行匹配——同样对于每一个需要匹配的字符串我们用一个指针来指向它需要匹配的字符,那么在遍历字符串 s 的过程中,对于当前遍历到的字符如果有可以匹配的字符串,那么将对应的字符串指针往后移动一单位即可。那么当字符串 s 遍历结束时,字符串数组中全部字符串的匹配情况也就全部知道了。
3.代码实现(Java)
//思路1————判断子序列
//双指针法
class Solution {
public int numMatchingSubseq(String s, String[] words) {
int res = 0;
int n = words.length;
int sLen = s.length();
for (String word : words) {
if (isSubsequence(word, s)) {
res++;
}
}
return res;
}
//判断 s 是否为 t 的子序列,如果是则返回 true,否则返回 false
public boolean isSubsequence(String s, String t) {
//双指针法
int i = 0;
int j = 0;
int sLen = s.length();
int tLen = t.length();
while (i < sLen && j < tLen) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == sLen;
}
}
//二分搜索法
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<Integer>();
}
for (int i = 0; i < s.length(); ++i) {
pos[s.charAt(i) - 'a'].add(i);
}
int res = words.length;
for (String w : words) {
if (w.length() > s.length()) {
--res;
continue;
}
int p = -1;
for (int i = 0; i < w.length(); ++i) {
char c = w.charAt(i);
if (pos[c - 'a'].isEmpty() || pos[c - 'a'].get(pos[c - 'a'].size() - 1) <= p) {
--res;
break;
}
p = binarySearch(pos[c - 'a'], p);
}
}
return res;
}
public int binarySearch(List<Integer> list, int target) {
int left = 0, right = list.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (list.get(mid) > target) {
right = mid;
} else {
left = mid + 1;
}
}
return list.get(left);
}
}
//思路2————多指针
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Queue<int[]>[] queue = new Queue[26];
for (int i = 0; i < 26; i++) {
queue[i] = new ArrayDeque<int[]>();
}
for (int i = 0; i < words.length; i++) {
queue[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});
}
int res = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int len = queue[c - 'a'].size();
while (len > 0) {
int[] t = queue[c - 'a'].poll();
if (t[1] == words[t[0]].length() - 1) {
res++;
} else {
t[1]++;
queue[words[t[0]].charAt(t[1]) - 'a'].offer(t);
}
len--;
}
}
return res;
}
}
相关文章
- LeetCode:搜索二维矩阵题解
- 【LeetCode】 课程表 [M](拓扑排序)
- 【LeetCode】整数反转 [M](数学)
- 【LeetCode】单词接龙 II [H](宽搜和深搜)
- 【LeetCode】数组中两个数的最大异或值 [M](前缀树)
- 【LeetCode】无重复字符的最长子串 [M](动态规划)
- 【LeetCode】奇怪的打印机 [H](记忆化搜索)
- 【LeetCode】将N叉树编码为二叉树(使用深度优先递归)
- 【LeetCode】翻转对
- LeetCode_排序_二分搜索_双指针_中等_658.找到 K 个最接近的元素
- LeetCode_二分搜索_中等_436.寻找右区间
- LeetCode_栈_中等_227.基本计算器 II(不含括号)
- LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索
- LeetCode_动态规划_二分搜索_耐心排序_中等_300.最长递增子序列
- LeetCode_二分搜索_中等_34.在排序数组中查找元素的第一个和最后一个位置
- LeetCode 88 合并两个有序数组
- LeetCode·392.判断子序列·动态规划
- LeetCode·707.设计链表·架构题
- leetcode第一刷_Simplify Path
- LeetCode-35. 搜索插入位置(Golang实现)
- [LeetCode] 349. Intersection of Two Arrays 两个数组相交
- [LeetCode] 270. Closest Binary Search Tree Value 最近的二叉搜索树的值
- [LeetCode] 173. Binary Search Tree Iterator 二叉搜索树迭代器
- [LeetCode] 95. Unique Binary Search Trees II 唯一二叉搜索树 II
- leetcode算法: Find Largest Value in Each Tree Row
- leetcode算法:Distribute Candies
- leetcode 35 搜索插入位置
- leetcode 93 复原IP地址
- leetcode 450删除二叉搜索树中的节点