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;}

若代码出现错误,可查看:http://tech.yushuai.xyz/2019/10/15/leetcode191014/