[LeetCode]Is Subsequence

双指针即可解决，即使T中存在多个S子序列我们依然可以找到第一个。假设S长M，T长N，时间复杂度O(M + N)，常数空间。代码如下：

	class Solution {
	public:
	bool isSubsequence(string s, string t) {
	int lenS = s.size(), lenT = t.size(), i = 0, j = 0;
	if(lenS > lenT)return false;
	while(i < lenS && j < lenT)
	{
	if(s[i] == t[j])
	++i;
	++j;
	}
	return i == lenS;
	}
	};

view raw Is Subsequence_1.cpp hosted with ❤ by GitHub

对于Follow up的问题，当我们用来query的S序列很多个，我们如何优化。一般对于这种问题，我们一般是用某种数据结构对T进行预处理来省下一些时间。我们要保证S是T的子序列的话，对于S中的字符s[i]，其在T中的位置为可能存在多个位置，那么对应每一个字符，我们选择其在T 中的某个位置，我们可以得到一串序列，如果这个序列是递增的，代表S是T的子序列。根据这个思路，我们对T进行预处理，统计每个字符出现的index，存入数组中，这个数组是sorted的，对于每一个字符，我们binary search符合要求的字符（当前数组中大于我们之前找到的index的最小值）。鉴于字符的种类是有限的，假设我们只用字母，时间复杂度为M * log(26) = O(M)。我们节省了要每次扫T的时间，代码如下：

	class Solution {
	public:
	bool isSubsequence(string s, string t) {
	int lenS = s.size(), lenT = t.size(), i = 0, j = 0;
	if(lenS > lenT)return false;
	unordered_map<char, vector<int>> map;
	for(int i = 0; i < lenT; ++i)
	map[t[i]].push_back(i);
	int prev = -1;
	for(int i = 0; i < lenS; ++i)
	{
	if(map.find(s[i]) == map.end())
	return false;
	int next = binarySearch(map[s[i]], prev);
	if(next == -1)
	return false;
	prev = next;
	}
	return true;
	}
	private:
	int binarySearch(vector<int>& v, int lowBound)
	{
	int lo = 0, hi = v.size() - 1;
	while(lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(v[mid] <= lowBound)
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	return lo == v.size()? -1: v[lo];
	}
	};

view raw Is Subsequence_2.cpp hosted with ❤ by GitHub