LeetCode 792. Number of Matching Subsequences

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2018/03/09/LeetCode-792-Number-of-Matching-Subsequences/

访问原文「LeetCode 792. Number of Matching Subsequences

题目要求

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
Output: 3
Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.

Note:

  • All words in words and S will only consists of lowercase letters.
  • The length of S will be in the range of [1, 50000].
  • The length of words will be in the range of [1, 5000].
  • The length of words[i] will be in the range of [1, 50].

题意解析

现在有一个字符串S和一个单词字典words,求出words满足是S子序列的单词数目。

解法分析

首先定义一个数组index,长度为words的长度,indexindex[i]代表words[i]接下来应当匹配是否在S中出现的字符位置,初始化都为0。当words[i]满足为S子序列时,index[i]=-1
S的字符从前到后开始遍历,假设当前为S[j],遍历index:

  1. index[i] == -1时,continue;
  2. S[j] == words[i].charAt(index[i])时,index[i]++;
  3. index[i] >= words[i].length(),满足条件,总数加1,并且index[i] = -1
    需要注意的是,如果上一轮S[j]时,没有任何words[i].charAt(index[i])S[j],则当S[j + 1] == S[j]时直接跳过此轮。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int numMatchingSubseq(String S, String[] words) {
int sum = 0;
int[] index = new int[words.length];
for (int i = 0; i < words.length; i++) {
index[i] = 0;
}
boolean hasMatch = false;
char[] cs = S.toCharArray();
for (int m = 0; m < cs.length; m++) {
char c = cs[m];
if (!hasMatch && m > 0 && cs[m - 1] == c) {
continue;
}
if (hasMatch) hasMatch = false;
for (int i = 0; i < words.length; i++) {
if (index[i] == -1) {
continue;
}
if (c == words[i].charAt(index[i])) {
index[i]++;
if (index[i] >= words[i].length()) {
sum++;
index[i] = -1;
hasMatch = true;
}
}
}
}
return sum;
}
Jerky Lu wechat
欢迎加入微信公众号