给定字符串 s 和字符串数组 words, 返回 words[i] 中是 s 的子序列的单词个数。

字符串的子序列是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是 none)，而不改变其余字符的相对顺序。

例如， “ace” 是 “abcde” 的子序列。

示例 1：
输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。

示例 2：
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2

提示：
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。

思路

对于字符串s和字符串t，若s为t的子序列，则需要满足以下几点：

  • s中的所有字符的相对顺序，必须和这些字符在t中出现的相对顺序保持一致，例如s为ace，t为abcde，则s为t的子序列，此时a、c、e三个字符在两个字符串中出现的相对顺序保持一致，t可以通过删除b和d两个字符来得到s。
  • 若s由一个或多个相同字符组成，那么该字符在s中出现的次数必然小于等于t中该字符出现的次数，例如字符串a、aa、aaa均为字符串aabade的子序列，但aaaa不是字符串aabade的子序列。

那么，维护一个数组，记录下原字符串t中每一个字符t[i]出现的位置i，然后对于要判断子序列的样本s，遍历s的每个字符，判断以下几点：

  • 如果对于当前字符s[i]，数组中找不到对应的位置记录，则说明s[i]字符在t中不曾出现，不满足子序列要求。
  • 如果能够找到对应的位置记录，则说明s[i]字符在t中有出现，需要判断s[i]字符在t中出现的个数，如果超过t中出现该字符的个数，不满足子序列要求。
  • 如果对于字符串s，上面两点均满足子序列的要求，则说明当前字符串s在[0,i]位置的字符构成的字符串已满足子序列要求，指针向后遍历下一个s[i+1]字符，同时，由于相对顺序保持一致，将j向后移动，s[i+1]将和t[i+1]进行判断。

代码实现

 public static int numMatchingSubseq(String s, String[] words) {
        return numMatchingSubseqByLeftBondBinarySearch(s, words);
    }

    /**
     * @Author huang.zh
     * @Description //二分查找解法，判断子序列个数
     * @Date 10:21 PM 2023/9/9
     * @Param [s, words]
     * @return
     **/
    private static int numMatchingSubseqByLeftBondBinarySearch(String s, String[] words){
        ArrayList<Integer>[] arrays = new ArrayList[26];
        int sLength = s.length();
        //对原样本进行预处理，记录s中每一个字符出现的下标位置
        for (int i = 0; i < sLength; i++) {
            int index = s.charAt(i) - 'a';
            if (arrays[index] == null)
                arrays[index] = new ArrayList<>();
            //记录当前字符s[i]对应的位置i
            arrays[index].add(i);
        }
        int result = 0;
        for (String word : words) {
            if (isSubSequence(word,arrays))
                result++;
        }
        return result;
    }

    /**
     * @Author huang.zh
     * @Description 判断s是否为子序列
     * @Date 10:31 PM 2023/9/9
     * @Param [s, arrays]
     * @return
     **/
    private static boolean isSubSequence(String s,ArrayList<Integer>[] arrays){
        //定义指针j，在搜寻过程中每找到一个字符就向后移动一位，确保s中每个字符的相对顺序必须和原字符串中一致，才能算作子序列
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (arrays[index] == null)
                //当前字符在原字符串中没出现过，肯定不是子序列
                return false;
            //搜寻当前字符在原字符串中第一次出现的位置
            //由于子序列的相对顺序必须和原字符串一致，所以point一定会落在[0,arrays[index].size())内
            int point = leftBondBinarySearch(arrays[index], j);
            if (point == arrays[index].size())
                //防止重复字符超出原字符中同字符的长度上限，比如原字符为aa，s为aaa，显然不符合子序列
                return false;
            //当前字符满足条件，将j指针往后移动，用于下一个字符判断
            j = arrays[index].get(point)+1;
        }
        return true;
    }

    /**
     * @Author huang.zh
     * @Description 找到数组中第一个值为target的元素下标
     * @Date 10:23 PM 2023/9/9
     * @Param [list, target]
     * @return
     **/
    private static int leftBondBinarySearch(ArrayList<Integer> list,int target){
        //注意high的取值，代表在左闭右开区间[low,high)中去搜寻第一个符合的元素
        int low = 0,high = list.size();
        while (low < high){
            int mid = low + (high - low)/2;
            Integer value = list.get(mid);
            if (value == target){
                //命中，但是要向前搜索第一个元素
                //这里high赋值为mid，代表后续将在左闭右开区间[low,mid)即闭区间[low,mid-1]中搜寻
                high = mid;
            } else if (value > target){
                high = mid;
            } else {
                low = mid+1;
            }
        }
        return low;
    }

    public static void test(){
        System.out.println(numMatchingSubseq("abcde",new String[]{"a","bb","acd","ace"}));
        System.out.println(numMatchingSubseq("dsahjpjauf",new String[]{"ahjpjau","ja","ahbwzgqnuk","tnmlanowax"}));
        System.out.println(numMatchingSubseq("aa",new String[]{"aaa"}));
    }