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的长度，index中index[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]时直接跳过此轮。

解题代码

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;

}