LeetCode 771. 宝石与石头Jewels and Stones

题目描述

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

题目分析

这道题比较简单，姑且当作长久未碰C++的一次练手吧。从题目中可以看出，无非就是字符串搜索，而且是简单的搜索。如果采用暴力搜索，即每个S中的字符和每个J中的字符比较，那么时间复杂度应该是O(n*m)，n、m表示S、J的长度。由于题目中规定S、J的长度都不会超过50，50*50=2500，其实还好，，这点小数据是不会造成LTE的。

但实际上可以利用一个map标记哪些字符算宝石。首先通过扫描一遍J字符串确定所有宝石字符，然后再扫描一遍S字符串看总共包含了多少宝石。这里我借用了字符与ASCII码的关系，用ASCII码表示字符，因此可以很容易的用数组来实现。时间复杂度显然是O(n+m)。代码如下：

Solution

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int result = 0;
        bool map[200];
        for (int i = 0; i < 200; i++) { map[i] = false; }
        for (int i = 0; i < J.length(); i++) {
            map[J[i]] = true;
        }
        for(int i = 0; i < S.length(); i++) {
            if(map[S[i]]) result++;
        }
        return result;
    }
};

结果

可以看出效率是很高了。