給定一個字符串S 和一個單詞字典 words馏慨，問, words中一共有多少個單詞words[i]是字符串S的子序列?
注意, 子序列不同于子串, 子序列不要求連續(xù).
number-of-matching-subsequences
樣例
樣例 1:
輸入: S = "abcde", words = ["a", "bb", "acd", "ace"]
輸出: 3
解釋: words內(nèi)有三個單詞是S的子串: "a", "acd", "ace".
樣例 2:
輸入: S = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
輸出: 2
思路1
遍歷數(shù)組得到 target 與 s 進(jìn)行對比绍刮，在 s 中找到 target 的每個字符的下表索引，如果為 -1 證明不存在饲宿，則不是 s 的子串。
思路2
遍歷數(shù)組得到 target 與 s 進(jìn)行對比，設(shè)置 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();
}
}
