number-of-matching-subsequences

给定一个字符串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();
    }

}

Github https://github.com/xingfu0809/Java-LintCode