Today is the first time to write algorithm problem solving, in fact, I also started to brush problems recently, I did not have this habit before. Programmers brush questions like uncle pancake pancake, a day without dozens of fried feeling can not mix in this line. I began to brush questions because a number of big factory friends have this habit, I suddenly realized that I do not brush questions can also used to the situation is really a lot of ah! The reason why dachang is a big factory is because other people are really making pancakes, and I am just a cashier of Uncle Pancake.

Since it’s the first question, it’s easier!

Title description:

Leetcode -771. Gems and Stones

Given the string J for the type of gem in the stone, and the string S for the stone you own. Each character in S represents a type of stone you own, and you want to know how many of the stones you own are gems.

The letters in J are not repeated, and all characters in J and S are letters. The letters are case sensitive, so “A” and “A” are different types of stone.

Example 1:

Input: J = “aA”, S = “aAAbbbb” Output: 3

Input: J = “z”, S = “ZZ” output: 0

S and J contain up to 50 letters. The characters in J are not duplicated.

Answer key:

This is a problem that most people know how to solve, and the general approach is like this:

/ * * *@param {string} J
 * @param {string} S
 * @return {number}* /
var numJewelsInStones = function(jewels, stones) {
    jewels = jewels.split(' ');
    return stones.split(' ').reduce((prev, val) = > {
        for (const ch of jewels) {
            if (ch === val) {
                return prev + 1; }}return prev;
    }, 0);
};
Copy the code

The idea is to iterate over each character of the stone and determine if each character is a gem. But the complexity is high, if the stone is length X and the gem is length Y, the time complexity is O(xy);

Recommended solution:

/ * * *@param {string} J
 * @param {string} S
 * @return {number}* /
var numJewelsInStones = function(J, S) {
   const jewelsSet = new Set(J.split(' '));
    return S.split(' ').reduce((prev, val) = > {
        return prev + jewelsSet.has(val);
    }, 0);
};
Copy the code

The biggest difference is the use of THE ES6 hash Set. A Set is like an array, except that there are no duplicate values; Construct a Set that takes characters from a gem of length x as arguments. The time complexity is O(x); Iterating through the stone string of length Y, prev + jewelsset.has (val) determines if the character is present in the gem and automatically filters out duplicate characters. The trick here is that Number+ true is the same thing as Number+1, O(1); So it comes down to order x plus y.

From the perspective of spatial complexity, the first solution is O(1) and the second solution is O(x). It’s easy to understand that the former only stores one variable, and the latter uses a hash set, but the latter is obviously more efficient.

Hydrology ends here, hope useful to you! Do you want to guess what Number plus false is?

Reference link: leetcode-cn.com/problems/je…