共计 3091 个字符,预计需要花费 8 分钟才能阅读完成。
题目形容
这是 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
提醒:
- $1 <= s.length <= 5 \times 10^4$
- $1 <= words.length <= 5000$
- $1 <= words[i].length <= 50$
words[i]
和s
都只由小写字母组成。
预处理 + 哈希表 + 二分
奢侈断定某个字符串是为另一字符串的子序列的复杂度为 $O(n + m)$,对于本题共有 $5000$ 个字符串须要断定,每个字符串最多长为 $50$,因而整体计算量为 $(5 \times 10^4 + 50) \times 5000 \approx 2.5 \times 10^8$,会超时。
不可避免的是,咱们要对每个 $words[i]$ 进行查看,因而优化的思路可放在如何优化单个 $words[i]$ 的断定操作。
奢侈的断定过程须要应用双指针扫描两个字符串,其中对于原串的扫描,会有大量的字符会被跳过(有效匹配),即只有两指针对应的字符雷同时,匹配串指针才会后移。
咱们思考如何优化这部分有效匹配。
对于任意一个 $w = words[i]$ 而言,假如咱们以后匹配到 $w[j]$ 地位,此时咱们曾经明确下一个待匹配的字符为 $w[j + 1]$,因而咱们能够间接在 s
中字符为 $w[j + 1]$ 的地位中找候选。
具体的,咱们能够应用哈希表 map
对 s
进行预处理:以字符 $c = s[i]$ 为哈希表的 key
,对应的下标 $i$ 汇合为 value
,因为咱们从前往后解决 s
进行预处理,因而对于所有的 value
均满足递增性质。
举个 🌰 : 对于
s = abcabc
而言,预处理的哈希表为{a=[0,3], b=[1,4], c=[2,5]}
最初思考如何断定某个 $w = words[i]$ 是否满足要求:待匹配字符串 w
长度为 m
,咱们从前往后对 w
进行断定,假如以后判待匹配地位为 $w[i]$,咱们应用变量 idx
代表可能满足匹配 $w[0:i]$ 的最小下标(贪婪思路)。
对于匹配的 $w[i]$ 字符,能够等价为在 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<String, Array<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.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
- 工夫复杂度:令
n
为s
长度,m
为words
长度,l = 50
为 $words[i]$ 长度的最大值。结构map
的复杂度为 $O(n)$;统计符合要求的 $words[i]$ 的数量复杂度为 $O(m \times l \times \log{n})$。整体复杂度为 $O(n + m \times l \times \log{n})$ - 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.792
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布