Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/jewels-and-stones/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một chuỗi jewels đại diện cho những viên đá quý, và chuỗi stones đại diện cho những cục đá bạn có. Mỗi chữ cái trong chuỗi stones là một loại đá mà bạn có. Hãy tìm ngọc ẩn trong chuỗi stones bạn có.
Các chữ cái phân biệt chữ hoa chữ thường, vì vậy "a" được coi là một loại đá khác với "A".

Điều kiện:

  • 1 <= jewels.length, stones.length <= 50.
  • jewels và stones chỉ bao gồm các chữ cái tiếng Anh.
  • Tất cả chữ cái trong jewels là duy nhất không trùng lặp.

Ví dụ 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Ví dụ 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

3. Phân tích

Âu kề, đề bài sẽ cho bạn chuỗi jewels là các loại đá quý để bạn nhận diện xem có xuất hiện ở trong những cục đá stones mà bạn đang có không. Bài này cũng không quá phức tạp. Chúng ta sẽ xử lý bài này với cấu trúc dữ liệu HashSet.
Chúng ta bỏ những viên đá quý từ jewels vào trong set, sau đó duyệt qua cục đá stones kia, kiểm tra từng cục đá xem có cái nào giống với mỗi viên đá quý từ set không? Nếu có thì ta đếm thêm 1, không có thì thôi mò cục đá tiếp theo đến khi hết.
Đó, quá là đơn giản luôn! Bước tiếp theo!

4. Code chạy bằng cơm

Đầu tiên chúng ta sẽ tạo ra một HashSet để chứa những viên đá quý từ jewels:
leetcode-771-1

Giờ chúng ta chuyển đổi cục đá to stones thành các cục đá nhỏ hơn dưới dạng mảng các chữ cái arr:
leetcode-771-2

Tại vị trí con trỏ i đang đứng, chúng ta thấy cục đá nhỏ 'a' này giống với viên đá quý 'a' ở trong set nên đếm được 1 viên đá quý:
leetcode-771-3

Tại i = 1 và i = 2, ta lại thấy cục đá nhỏ 'A' này giống với viên đá quý ở trong set, nên đếm thêm được 2 viên đá quý, vậy hiện tại ta đang có 3 viên:
leetcode-771-4

Và khi i chạy đến cuối mảng, chúng ta không thấy cục đá nào giống với những viên đá quý nữa, vậy là chúng ta chỉ có 3 viên đá quý từ trong những cục đá mà thôi.

5. Code luôn thôi

Và code của chúng ta sẽ như sau:

 public int numJewelsInStones(String jewels, String stones) {
     Set<Character> myset = new HashSet<>();

     for (Character c : jewels.toCharArray()) {
         myset.add(c);
     }
     
     int count = 0;
     char[] arr = stones.toCharArray();

     for (char c : arr) {
         if(myset.contains(c)){
             count++;
         }
     }

     return count;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!