number-of-matching-subsequences
2019-07-22 本文已影响0人
龙潭吴彦祖丶
给定一个字符串S 和一个单词字典 words，问, words中一共有多少个单词words[i]是字符串S的子序列?
注意, 子序列不同于子串, 子序列不要求连续.
number-of-matching-subsequences
样例
样例 1:
输入: S = "abcde", words = ["a", "bb", "acd", "ace"]
输出: 3
解释: words内有三个单词是S的子串: "a", "acd", "ace".
样例 2:
输入: S = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2
思路1
遍历数组得到 target 与 s 进行对比，在 s 中找到 target 的每个字符的下表索引，如果为 -1 证明不存在，则不是 s 的子串。
思路2
遍历数组得到 target 与 s 进行对比，设置 index 为 target 索引， i 为 s 的索引，
if (target.charAt(index) == s.charAt(i)) {
index++;
}
最后判断 index == target.length 如果相等是子串，如果不相等就不是子串。
public class Solution {
/**
* @param s: a string
* @param words: a dictionary of words
* @return: the number of words[i] that is a subsequence of s
*/
public int numMatchingSubseq(String s, String[] words) {
// Write your code here
if (words == null || words.length == 0) {
return 0;
}
int result = 0;
for (String item : words) {
if (isMatching( item,s)) {
result++;
}
}
return result;
}
private boolean isMatching(String target, String s) {
int temp = 0;
for (int i = 0; i < target.length(); i++) {
int indexOf = s.indexOf(target.charAt(i), temp);
if (indexOf == -1) {
return false;
}
temp = indexOf+1;
}
return true;
}
}
public class Solution{
public int numMatchingSubseq(String S, String[] words) {
int result = 0;
for (String target : words) {
if (isMatching(target, S)) {
result++;
}
}
return result;
}
private boolean isMatching(String target, String s) {
int index = 0;
int i = 0;
while (index < target.length() && i < s.length()) {
if (target.charAt(index) == s.charAt(i)) {
index++;
}
i++;
}
return index == target.length();
}
}
