LeetCode 392. 判断子序列 简单

我的解题

这是按照 labuladong 二分查找的妙用：判定子序列 中的思路所写。

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        /**
         * 首先预处理t
         * index记录了t中字符的位置信息
         */
        vector<vector<int>> index(256); // 共256个字符
        int n = t.size();
        for (int i = 0; i < n; ++i)
        {
            index[t[i]].push_back(i);
        }
        int j = 0;
        int m = s.size();
        for (int i = 0; i < m; ++i)
        {
            char c = s[i];
            if (index[c].size() == 0) // t中不包含c
            {
                return false;
            }
            else // t中包含c
            {
                int pos = left_bound(index[c], j); // 寻找t中的所有c中，位于j后的c的位置
                if (pos == index[c].size())
                {
                    return false;
                }
                j = index[c][pos] + 1;
            }
        }
        return true;
    }
    /**
     * @brief 二分查找左侧边界
     *
     * @param arr
     * @param target
     * @return
     */
    int left_bound(std::vector<int> arr, int target)
    {
        int left = 0, right = arr.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
            {
                right = mid - 1;
            }
            else if (arr[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left;
    }
};

int main()
{
    std::string s = "abc", t = "ahbgdc";
    Solution solu;
    solu.isSubsequence(s, t);
}