二分查找高效判定子序列 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：二分查找高效判定子序列

评论礼仪 见这里，违者直接拉黑。

[YJM1024]

预处理的时间是O(N)吧。

[JaronZou]

题目假设有大量的 S 输入，而 T 是不变的。对于大量的 S 输入来说，T 的预处理时间可以忽略了。

[YJM1024]

可以用HashMap做。把一系列字符串的第一个字符加入HashMap并且记录是哪个字符串。然后遍历t，对于匹配到的字符串，把它们的下一个字符加入HashMap直到末尾。时间复杂度是O(M*N)。M是字符串数量，N是t的长度。

[YJM1024]

哦。时间复杂度好像不对……

[zhongweiLeex]

防止大家对这边的 index[c] 这种表达形式转不过弯来， 这边使用HashMap实现了一下

class Solution {
    public boolean isSubsequence(String s, String t) {
        TreeMap<Character,LinkedList<Integer>> map = new TreeMap<>();//存储t中所有 与s中字符相同的字符的索引位置
        // char - list[字符索引]

        for(int i = 0; i<t.length();i++){
        LinkedList<Integer> list = new LinkedList<>();
            if(map.containsKey(t.charAt(i))){//如果存在 直接在list末尾添加
                map.get(t.charAt(i)).add(i);
            }else{
                list.addLast(i);//如果不存在需要创建一个键值映射
                map.put(t.charAt(i),list);
            }
        }

        int j = 0;//t中的游标位置
        for(int i = 0; i< s.length();i++){
            char c = s.charAt(i);// 当前s中需要匹配的字符
            if(!map.containsKey(c)){//t中没有这个字符 直接返回false
                return false;
            }
            //如果存在，找到比当前游标位置 大的 最小的索引
            int pos = leftBound(map.get(c),j);
            // System.out.println(pos); debug位置 
            //  System.out.println("---");
            if(pos == map.get(c).size()) return false;
            j = map.get(c).get(pos) +1; //t上的指针
            // System.out.println(j);debug 位置
        }
        return true;
    }
    //寻找s中字符  在t中字符索引 的 左边界
    //list中存储的是 s中c字符对应的 所有索引 从小到大排序
    //我们要找的是list中比  当前t上指针 j/tar 大的那个索引 直接跳过去
    //这里得出的 左边界是  存储 对应字符索引的 list 的索引  所以，如果想要得到 对应t上的实际位置  还需要使用get(pos)
        private int leftBound(LinkedList<Integer> list,int j){
            int left = 0;
            int right = list.size();
            while(left < right){
                int mid = (right - left)/2 + left;
                if(j>list.get(mid)){
                    left = mid+1;
                }else{
                    right = mid;
                }
            }
            return left;
        }
}

[zdcat]

我选择index[c]

[gp868]

还可以用动态规划做

[Maxiah]

这题也可以归并到LCS的问题

[Maxiah]

贴个C++的用哈希表的代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 二分查找
        
        int m = s.size(), n = t.size();
        // 将较长的字符串保存到map里去
        unordered_map<char,vector<int>> map_t(256);
        for(int i = 0; i < n; i++){
            map_t[t[i]].push_back(i);
        }
        // a 0
        // h 1
        // b 2
        // g 3
        // d 4
        // c 5
        
        // 串t指针
        int j = 0;
        // 借助map查找s[i]
        for(int i = 0; i < m; i++){
            if(!map_t.count(s[i])){
                // s[i]不在t里，直接返回
                return false;
            }
            // 如果存在，在map[s[i]]中搜索比j大的最小索引即可：即二分搜索左侧边界的结果值
            int pos = leftBound(map_t[s[i]], j); // 传入的是s[i]在t中对应出现的所有下标索引
            if(pos == map_t[s[i]].size()){
                // 二分搜索区间中没有找到s[i]
                return false;
            }
            j = map_t[s[i]][pos] + 1; // j 移动到二分搜索返回的pos处 后一位
        }
        return true;
    }

    int leftBound(vector<int>& vec_t, int j){
        // 二分查找 搜索左侧边界 搜索j
        int left = 0, right = vec_t.size();
        // 左闭右开
        while(left < right){
            int mid = left + (right - left)/2;
            if(vec_t[mid] < j){
                left = mid + 1;
            }else if(vec_t[mid] >j){
                right = mid;
            }else{
                right = mid;
            }
        }

        return left;
    }
};

[deepbreath373]

结束啦

[lhcezx]

跟着东哥刷完了，每道题都手敲了一遍，祝各位秋招好运

[labuladong]

牛逼，加油💪🏻

[Velliy]

打卡一刷结束 秋招加油

[labuladong]

加油💪🏻💪🏻

[SUN7700]

秋招怎么样了兄弟

[Alwin4Zhang]

792 题「 匹配子序列的单词数」 python version

from collections import defaultdict
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        char2idx = defaultdict(list)
        for i, c in enumerate(s):
            char2idx[c].append(i)

        def left_bound(arr, target):
            left, right = 0, len(arr)
            while left < right:
                mid = left + (right - left) // 2
                if arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            if left == len(arr):
                return -1
            return left

        res = 0  # 记录有几个是子序列
        for word in words:
            i, j = 0, 0
            for c in word:
                idxs = char2idx.get(c)
                if not idxs:
                    break
                pos = left_bound(idxs, j)
                if pos == -1:
                    break
                j = idxs[pos] + 1
                i += 1
            if i == len(word):
                res += 1
        return res

[XiaofanLinUS]

typescript 一刷结束了 感谢东哥， 接下来用c++二刷，中途顺便参加下打卡活动。 大家加油！

[labuladong]

牛，加油💪🏻

[15332318025]

392 利用字符串查找函数也可以实现【C语言】

bool isSubsequence(char * s, char * t){
    int len = strlen(s);
    char *p = t;
    for (int i = 0; i < len; i++) {
        p = strchr(p, s[i]);
        if (p == NULL) {
            return 0;
        }
        p++;
    }

    return 1;
}

[15332318025]

792 匹配子序列的单词数 ，循环遍历一下392即可【C语言】

// 判断一个字符串是否是另一个字符串的子序列
bool IsSubSeq(char *words, char *s)
{   
    char *p = s;
    int len = strlen(words);
    for (int i = 0; i < len; i++) {
        p = strchr(p, words[i]);
        if (p == NULL) {
            return 0;
        }
        p += 1;
    }

    return 1;
}

int numMatchingSubseq(char * s, char ** words, int wordsSize){
    int num = 0;
    for (int i = 0; i < wordsSize; i++) {
        if (IsSubSeq(words[i], s)) {
            num++;
        }
    }

    return num;
}

[yuanjunfang]

肝了一个月，跟着刷完一遍了，刚刚入门，但是记得不深刻，还得再来一两遍，加油

[Chris-zhang1]

为啥代码过不去啊

[zenyanggongmian1995]

  int numMatchingSubseq(String s, String[] words) {

    int res = 0;

    // 对 s(母串) 进行预处理
    // char -> 该 char 的索引列表
    ArrayList<Integer>[] index = new ArrayList[256];

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (index[c] == null) { // 这里c自动类型转换为ASC码
        index[c] = new ArrayList<>();
      }
      index[c].add(i); // 实现了类似hashmap的效果。
    }

    // todo 遍历数组中的每个单词。
    for (String word : words) {
      // 指向s
      int i = 0;
      // 指向Word
      int j = 0;

      // 遍历每个字符串
      while (j < word.length()) {
        char c = word.charAt(j);

        // todo 母串有这个字符，但是这个字符可能出现在母串的前面或者后面的任意位置。
        //  所以这里我们搜索母串这个字符的索引list，查看当前i位置有没有被记录，
        //  如果记录了更好，没记录就直接找到最近的一个记录位置。（至少说明是匹配上了，所以我们可以直接跳转到最近一个记录位置的下个位置）
        int pos = left_bound(index[c], i);
        if (pos == -1) {
          break;
        }

        // 至少说明是匹配上了，所以我们可以直接跳转到最近一个记录位置的下个位置。
        i = index[c].get(pos) + 1;

        // 移动单词上的指针，准备取出下一个字符和母串匹配。
        j++;
      }

      // 如果 word 完成匹配，则是子序列
      if (j == word.length()) {
        res++;
      }

    }

    return res;
  }

  int left_bound(ArrayList<Integer> arr, int target) {
    
    if (arr == null // 说明母串中没有这个字符。
        || arr.size() == 0 // 习惯而已，这里其实没有必要写，相当于也是说明母串中没有这个字符。
        // || target<arr.get(0)
        || target > arr.get(arr.size() - 1)) {
      return -1;
    }

    int left = 0;
    int right = arr.size();
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (target == arr.get(mid)) {
        right = mid;
      } else if (target > arr.get(mid)) {
        left = mid + 1;
      } else if (target < arr.get(mid)) {
        right = mid;
      }
    }

    return left;
  }

说一个比较有意思的地方，通常我在使用二分搜索时，会把4个合法性校验放在第一步，或者放在调用二分搜索的主函数的第一步。但是这里突然发现 // || target<arr.get(0)不能加上，原因是因为调用target<arr.get(0),但是至少说明这个字符是存在的，只不过索引位置比较靠后。

[zenyanggongmian1995]

   // j指向Word，该位置上是c字符，而i指向母串，想看看i处是不是也是c字符。
        // 怎么做呢？
    //  方式1：暴力匹配，取出母串的当前字符呗，不是就往下移动母串字符，找到后停下，然后去移动j继续匹配,但是效率太低了。
    //  方式2：检查母串c字符上的的索引数组，查看里面有没有i，不仅可以快速确认里面有没有i，还方便跳跃检查下一个位置。

      //  1.母串就压根没这个字符数组，直接break，不再匹配这个单词。 arr = null || arr.size()0, 后面这个条件是我的习惯，这里没有必要,可以break了。
      //  2.母串中有这个字符数组，开始检索：
      //  本质上有3种情况：
          // 1.母串中有这个字符，但是在很靠后的位置,索引数组里面记录的每个索引的值都比较大，所以i索引小于数组中记录的第一个索引。i<arr.get(0)，跟情况4一样。
          // 2.母串中有这个字符，但是已经存在的索引都被之前匹配消耗了，即这个字符都是在很靠前的位置。i>arr.get(arr.size()-1),break
          // 3.母串中有这个字符，而且i确实被记录了，说明母串中i处字符跟Word中j指向的字符时一致的。（其实我们并不关心，）
          // 4.母串中有这个字符，但是i没有被记录，
            // 但是i处在这个字符对应的索引数组的中间位置，那靠近他的下一个位置就是一个满足要求的字符。
            // 所以我们不再关注下一个位置，而是直接跳跃到下下个位置即可。
            // 结合情况1，3,4使用查找左边界最合适。

[zenyanggongmian1995]

我主函数中是直接查的，字符不存在 放到了左边界搜索的第一步中的，注意个labuladong代码的区别。

[mghio]

int m = s.length(), n = t.length();

---->

int m = s.length, n = t.length();

[mghio]

题中提示只有小写字母

words[i]和 s 都只由小写字母组成。

数组 index 只需要申请 123 大小即可（字符 z 转为 int 后的值为 122）。

ArrayList<Integer>[] index = new ArrayList[123];

[shiboys]

二分法又被你小子给玩出了花

[Kailianghu]

没必要使用leftbound函数，普通的二分函数即可吧。