Jewels and Stones

题目链接

传送门

题目大意

给定两个字符串J和S,J中字符保证各不相同,求S中包含J中字符的个数。

解题思路

用set集合存储J中字符,接下来遍历S。
若当前字符出现在set集合中,则计数+1。
时间复杂度O(nlogn),空间复杂度O(n)。

特别感谢Jgirl_033的提醒,set底层红黑树实现,count的时间复杂度是logn,再加上外层的一次遍历,所以时间复杂度为nlogn.

参考代码

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int lengthJ = J.length();
        int lengthS = S.length();
        // 将J中字符存入set集合
        set<char> setJ;
        for (int index = 0; index < lengthJ; index ++) {
            setJ.insert(J[index]);
        }
        // 寻找S中出现在set集合中的元素个数
        int count = 0;
        for (int index = 0; index < lengthS; index ++) {
            if (setJ.count(S[index])) {
                count ++;
            }
        }
        return count;
    }
};

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图