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.
1import java.util.HashSet;
2import java.util.Set;
3
4public class JewelStones {
5 public int numJewelsInStones(String jewels, String stones) {
6 Set<Character> jewelSet = new HashSet<>();
7 for (char jewel : jewels.toCharArray()) {
8 jewelSet.add(jewel);
9 }
10 int count = 0;
11 for (char stone : stones.toCharArray()) {
12 if (jewelSet.contains(stone)) {
13 count++;
14 }
15 }
16 return count;
17 }
18
19 public static void main(String[] args) {
20 JewelStones solution = new JewelStones();
21 System.out.println(solution.numJewelsInStones("aA", "aAAbbbb"));
22 }
23}The Java implementation uses a HashSet to store jewel types for O(1) average-time membership checks. The count is incremented for each stone appearing in this set.
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
class Program {
public static int NumJewelsInStones(string jewels, string stones) {
int[] jewelCount = new int[52];
foreach (var jewel in jewels) {
if (jewel >= 'a' && jewel <= 'z')
jewelCount[jewel - 'a'] = 1;
else
jewelCount[jewel - 'A' + 26] = 1;
}
int count = 0;
foreach (var stone in stones) {
if (stone >= 'a' && stone <= 'z') {
count += jewelCount[stone - 'a'];
} else {
count += jewelCount[stone - 'A' + 26];
}
}
return count;
}
static void Main() {
Console.WriteLine(NumJewelsInStones("aA", "aAAbbbb"));
}
}This C# implementation creates a 52-slot array that acts like a map from characters to a boolean jewel indicator, processed efficiently through array indexing based on character value.