Leetcode 647：回文子串
题目描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例
示例 1:
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".
示例 2:
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
题目思想
这里我的思路就是分为了两步：第一步提取出该字符串的所有子串；第二步，对每个子串判断是否是回文，若是则计数。最后返回结果。
但是这种方法复杂度太高，因为重复计算了太多。可以使用一种名为中心扩展的方法。这种方法的思路是选定一个点i，然后分别以i及(i,i+1)向两边扩展开始计算。这种扩展的思路就在countNums()函数中得以实现。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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++。
代码实现
| 1 2 3 4 5 6 7 8 9 10 | 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/
