LeetCode 771. Jewels and Stones

September 11, 2020

The minimum time for any solution to this is $O(J+S)$ since we have to look at every element of both inputs at least once.

We can solve it in $O(J+S)$ if we:

Hash the characters of $J$ (we can use a set).
Check if each character of $S$ is in $J$ and keep a count.

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.numJewelsInStones("aA", "aAAbbbb"), 3)
        self.assertEqual(self.s.numJewelsInStones("z", "ZZ"), 0)

    def test_simple(self):
        self.assertEqual(self.s.numJewelsInStones("x", "aEOrEjfkXxxaeirosex"), 3)

class Solution:

    def numJewelsInStones(self, J: str, S: str) -> int:
        j = set(J)
        count = 0
        for c in S:
            if c in j:
                count += 1
        return count

if __name__ == "__main__":
    unittest.main()