Leetcode 647：回文子串

题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例

示例 1:

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
示例 2:

输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

题目思想

这里我的思路就是分为了两步：第一步提取出该字符串的所有子串；第二步，对每个子串判断是否是回文，若是则计数。最后返回结果。
但是这种方法复杂度太高，因为重复计算了太多。可以使用一种名为中心扩展的方法。这种方法的思路是选定一个点i，然后分别以i及(i,i+1)向两边扩展开始计算。这种扩展的思路就在countNums()函数中得以实现。

代码实现

int countNums(string& s, int i, int j)
{
	if (i > j || i < 0 || j >= s.size())
		return 0;
	int nums = 0;
	while (i >= 0 && j < s.size() && s[i] == s[j])
	{
		--i;
		++j;
		++nums;
	}
	return nums;
}
int countSubstrings(string s)
{
	int res = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		res += countNums(s, i, i);
		res += countNums(s, i, i + 1);
	}
	return res;
}

Leetcode 771：宝石与石头

题目描述

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。

示例

示例 1:输入: J = “aA”, S = “aAAbbbb”
输出: 3
示例 2:输入: J = “z”, S = “ZZ”
输出: 0

题目思想

这个题目思路很简单，我感觉没必要做太多解释。就是说，对于S中的每一个字母，看在J中是否存在，若存在则nums++。

代码实现

int numJewelsInStones(string J, string S) {
	int nums = 0;
	for (auto s : S)
	{
		if (J.find(s) != J.npos)//如果能找到这个字母
			nums++;
	}
	return nums;
}