题目:给定两个字符串 s 和 t ,它们只包含小写字母。 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。
示例 1: 输入:s = “abcd”, t = “abcde” 输出:“e” 解释:‘e’ 是那个被添加的字母。
示例 2: 输入:s = “”, t = “y” 输出:“y”
提示: 0 <= s.length <= 1000 t.length == s.length + 1 s 和 t 只包含小写字母
我们的思路是,首先以s字符串中的字符s[i]作为hash数组的下标,记录s[i]出现的次数;然后判断以t[i]作为hash数组的下标是否出现过,出现过则减去1,没出现过则是这个要返回的字符,把它的位置记录为1;最后在遍历一遍t字符串,hash位置等于1的位置即是不同的字符;
char findTheDifference(char* s, char* t)
{
//创建一个数组并初始化为0
int hash[26] = { 0 };
//将s字符串中的字符s[i]作为hash数组的下标,记录s[i]出现的次数
for (int i = 0; i < strlen(s); i++)
{
hash[s[i] - 'a'] += 1;
}
//遍历t字符串,判断以t[i]作为hash数组的下标是否出现过,出现过则减去1
//没出现过则是这个要返回的字符,把它的位置记录为1
for (int i = 0; i < strlen(t); i++)
{
if (hash[t[i] - 'a'])
hash[t[i] - 'a'] -= 1;
else
hash[t[i] - 'a'] = 1;
}
//再遍历一次t字符串,因为t与s字符串只相差一个字符,
//所以只有一个字符的hash数组位置被标记为1,其他都为0,返回为1的位置即可
for (int i = 0; i < strlen(t); i++)
{
if (hash[t[i] - 'a'] == 1)
{
return t[i];
}
}
return ' ';
}
题目:给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。 (例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
我们的思路是双指针,使用双指针遍历这两个字符串,i指向s,j指向t,如果找到相同的字符,i和j都往后走;如果不相同,j往后走;最后如果在j遍历完t字符串后,i还没有遍历完s字符串,证明s不是t的子序列;
bool isSubsequence(char* s, char* t)
{
//双指针
int i = 0, j = 0;
//只要有一个指针超出对应字符串长度的范围,就跳出循环
while (i < strlen(s) && j < strlen(t))
{
//如果找到相同的字符,i和j都往后走
if (s[i] == t[j])
{
i++;
}
//如果找不到,j往后走
j++;
}
//最后返回i是否等于s字符串的长度,
//当j走完t字符串,没有与s字符串中的字符匹配,i就没有遍历完s字符串,所以i就不会等于strlen(s),就会返回false
return i == strlen(s);
}