本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。
本次任务的知识点：贪心算法
贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
题号：392
难度：简单
https://leetcode-cn.com/problems/is-subsequence/
给定字符串s和t，判断s是否为t的子序列。
你可以认为s和t中仅包含英文小写字母。字符串t可能会很长（长度 ~= 500,000），而s是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
示例 3:
s = "", t = "ahbgdc"
返回 true.
后续挑战:
如果有大量输入的S，称作S1, S2, ... , Sk 其中k >= 10亿，你需要依次检查它们是否为T的子序列。在这种情况下，你会怎样改变代码？
第一种：贪心算法
贪心算法必须具备后无效性，也就是不必考虑前面的影响，只需考虑当前的状态。
若s = "abc", t = "ahbgdc" 要判断字符串s和t的排序是否一致，我们这样构造贪心策略：
取s中的第一个字符a，判断t中是否存在字符a
若存在，则判断t中字符a之后的剩余字符串是否存在第二个字符b
依次类推
用一句通俗的话就是剩余字符串中是否存在下一个字符，利用贪心算法的概念就是局部是否存在最优解。
执行结果：通过
执行用时：116 ms, 在所有 C# 提交中击败了 42.17% 的用户
内存消耗：43 MB, 在所有 C# 提交中击败了 7.41% 的用户
public class Solution
{
public bool IsSubsequence(string s, string t)
{
for (int i = 0; i < s.Length; i++)
{
int j = t.IndexOf(s[i]);
if (j == -1)
return false;
t = t.Substring(j + 1);
}
return true;
}
}
第二种：双指针法
利用两个变量i,j来记录搜索的位置，i记录搜索到t的位置，j记录搜索到s的位置，一旦j==s.Length表示s的字符全部搜索完成，即s是t的子序列，返回true即可。
执行结果：通过
执行用时：112 ms, 在所有 C# 提交中击败了 56.63% 的用户
内存消耗：38 MB, 在所有 C# 提交中击败了 25.93% 的用户
public class Solution
{
public bool IsSubsequence(string s, string t)
{
if (string.IsNullOrEmpty(s))
return true;
int j = 0;
for (int i = 0; i < t.Length; i++)
{
if (t[i] == s[j])
{
j++;
}
if (j == s.Length)
return true;
}
return false;
}
}
Python 语言
执行结果：通过
执行用时：268 ms, 在所有 Python3 提交中击败了 35.49% 的用户
内存消耗：18 MB, 在所有 Python3 提交中击败了 8.35% 的用户
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0:
return True
j = 0
for i in range(0, len(t)):
if t[i] == s[j]:
j += 1
if j == len(s):
return True
return False
联系客服
