Sponsored
Sponsored
This approach leverages a Set (or a HashSet in some languages) for quickly determining if a stone is a jewel. The idea is to store all the jewel types in a set, then iterate through each stone, checking if the stone is in the set. If it is, we increment our count of jewels found.
Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings.
1#include <stdio.h>
2#include <stdbool.h>
3
4bool isJewel(char c, char *jewels) {
5 for (int i = 0; jewels[i] != '\0'; i++) {
6 if (c == jewels[i]) {
7 return true;
8 }
9 }
10 return false;
11}
12
13int numJewelsInStones(char *jewels, char *stones) {
14 int count = 0;
15 for (int i = 0; stones[i] != '\0'; i++) {
16 if (isJewel(stones[i], jewels)) {
17 count++;
18 }
19 }
20 return count;
21}
22
23int main() {
24 char *jewels = "aA";
25 char *stones = "aAAbbbb";
26 printf("%d\n", numJewelsInStones(jewels, stones));
27 return 0;
28}
In the C implementation, we define a helper function isJewel
that checks if a character is a jewel by iterating through the jewel string. For each stone, we call this function and increment our count accordingly. This is not the most optimized as it involves iterating through the jewels for each stone.
This approach uses an array to quickly map each character to an index, allowing us to count frequencies of jewels in the stones. Since the input is restricted to English letters, a fixed-size array of 52 (for each upper and lower case letter) is adequate.
Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping.
1
The Python solution uses an indexed array for character analysis, distinguishing letters using ASCII values. This indexed approach facilitates concise membership checks.