leetcode-392. Is Subsequence-DP-NORMAL

给定字符串 s 和字符串 t，判断 s 是否是 t 的子序列。

两个字符串均只包含小写英文字母。t 可能非常长（长度约 500,000），s 较短（长度 <= 100）。

子序列是指从原字符串中删除若干字符（也可以不删除），且不改变剩余字符相对顺序而得到的新字符串。例如，"ace" 是 "abcde" 的子序列，而 "aec" 不是。

示例

• 示例 1：s = "abc"，t = "ahbgdc"，返回 true。
• 示例 2：s = "axc"，t = "ahbgdc"，返回 false。

进阶：如果有大量的 S 需要判断（S1, S2, …, Sk，k >= 1B），每次都要判断是否是 T 的子序列，如何优化代码？

可以使用 DP、贪心或二分查找来解决本题。

方法一：线性扫描（贪心）

最简单的做法：只需扫描 t 一遍，用一个指针跟踪 s 的匹配进度即可。

if (s == "")return true;

		int index = 0;
		for (int i = 0; i < t.size(); i++)
		{
			if (s[index] == t[i])
			{
				index++;
				if (index >= s.size())return true;
			}


		}

		return false;

方法二：暴力递归搜索

bool f(int a, int b)
{
	if (sa =="" )return true;

	if (a > sa.size())return true;//如果大于 那么表示前面所有的都匹配了因此true

	if (b > sb.size())return false;//b的index大于大小，意味着搜索完了还没return true因此false

	if (sa[a] == sb[b])//如果相同 那么直接递归下一个index
	{
		return f(a + 1, b + 1);
	}
	else
	{
		return    f(a, b + 1);//不同则移动sb的index
	}
}

方法三：将暴力递归转换为 DP

递推公式与递归公式相同，但循环方向需要逆向——因为递归是从底部返回的，所以递推要倒着来。

bool arr[10][10];//a b
	memset(arr, 0, 10 * 10);


	for (int b = 0; b < 10;b++)arr[0][b] = true;//初始化 字符串空

	for (int a = sa.size(); a < 10; a++)
	{
		for (int b =0; b < 10; b++)
		arr[a][b] = true; // 初始化a>sa.size的情况
	}
	for (int a =  sa.size() - 1;a>=0; a--)//递推求解，递推公式和递归公式一样，但是循环条件是逆向，因为递归到底以后是倒着返回来的，所以递推要倒着
	{
		for (int b = sb.size() - 1;b>=0; b--)
		{
			if (sa[a] == sb[b])
			{
				arr[a][b] = arr[a + 1][b + 1];
			}
			else
			{
				arr[a][b] = arr[a][b + 1];
			}
		}
	}


	cout << arr[0][0] << endl;
	cout << f(0, 0) << endl;