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;