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/count-the-number-of-vowel-strings-in-range/

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 mảng cách chuỗi tên word và hai số nguyên left và right.
Một chuỗi được gọi là vowel string (chuỗi nguyên âm) khi mà kí tự đầu tiên và kí tự cuối của chuỗi đó là nguyên âm. Cho bạn nào chưa biết thì bảng chữ cái tiếng Anh có 5 nguyên âm đó là 'u' 'e' 'o' 'a' 'i' (đọc là uể oải cho dễ nhớ).
Trả về kết quả là số chuỗi nguyên âm word[i] với điều kiện i nằm trong khoảng left và right.

Điều kiện bài toán:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 10
  • words[i] chỉ xuất hiện các chữ cái tiếng Anh viết thường.
  • 0 <= left <= right < words.length

Bài toán minh họa 1:

Input: words = ["are","amy","u"], left = 0, right = 2
Output: 2
Explanation: 
- "are" is a vowel string because it starts with 'a' and ends with 'e'.
- "amy" is not a vowel string because it does not end with a vowel.
- "u" is a vowel string because it starts with 'u' and ends with 'u'.
The number of vowel strings in the mentioned range is 2.

Bài toán minh họa 2:

Input: words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
Output: 3
Explanation: 
- "aeo" is a vowel string because it starts with 'a' and ends with 'o'.
- "mu" is not a vowel string because it does not start with a vowel.
- "ooo" is a vowel string because it starts with 'o' and ends with 'o'.
- "artro" is a vowel string because it starts with 'a' and ends with 'o'.
The number of vowel strings in the mentioned range is 3.

3. Phân tích

Ô kê đọc qua đề bài thì cũng không có gì quá đánh đố. Chúng ta chỉ cần đếm xem có bao nhiêu chuỗi word[i] là chuỗi nguyên âm, mà i thì nằm trong khoảng từ left đến right.

Ví dụ như ở bài toán minh họa 1
leetcode-2586-1
“are” bắt đầu bằng chữ ‘a’ và kết thúc bằng chữ ‘e’ nên nó được tính là chuỗi nguyên âm.

Sang bài toán minh họa 2, vì i nằm trong khoảng left = 1 đến right = 4 nên ta sẽ không xét đến từ “hey” (có index là 0).
leetcode-2586-2

Vậy thì chúng ta sẽ làm hai công việc chính để giải bài toán này:

  • Kiểm tra xem kí tự đầu và kí tự cuối của chuỗi trong mảng có phải là nguyên âm hay không.
  • Đếm số chuỗi đáp ứng đủ điều kiện.

Thế là xong! Triển tới bước tiếp theo!

4. Chạy code bằng cơm

Đầu tiên người ta cho mình cái mảng, nhưng chúng ta không nhất thiết phải duyệt toàn bộ mảng đó, chỉ cần chạy từ left tới right là được. Vậy thì vòng lặp sẽ có dạng:

for (int i = left; i <= right; i++) {
     // Code chạy ở đây       
}

Tiếp theo là chúng ta sẽ kiểm tra kí tự đầu và kí tự cuối của chuỗi đang được xét, chỉ cần dùng method charAt(i) là được:

char firstChar = string.charAt(0); // Kí tự đầu tiên sẽ có index bằng 0
char lastChar = string.charAt(string.length() - 1); // Kí tự cuối cùng sẽ có index bằng độ dài của chuỗi trừ 1.

Tiếp nữa ta phải kiểm tra xem firstChar và lastChar có phải nguyên âm hay không:

if(firstChar == 'u' || firstChar == 'e' || firstChar == 'o' || firstChar == 'a' || firstChar == 'i'
&& lastChar == 'u' || lastChar == 'e' || lastChar == 'o' || lastChar == 'a' || lastChar == 'i'
){
   return true; // Cả kí tự đầu và kí tự cuối đều phải là nguyên âm.
}

Vậy thì ta sẽ có code sơ bộ như sau:

public static int vowelStrings(String[] words, int left, int right) {
  int count = 0; // Biến này để đếm số lượng chuỗi đạt điều kiện đề bài

  for (int i = left; i <= right; i++) {
      if (checkWord1(words[i])) {
          count++;
      }
  }
  return count;
}

public static boolean checkWord(String str){
  char firstChar = str.charAt(0);
  char lastChar = str.charAt(str.length() - 1);
  if(firstChar == 'u' || firstChar == 'e' || firstChar == 'o' || firstChar == 'a' || firstChar == 'i'
      && lastChar == 'u' || lastChar == 'e' || lastChar == 'o' || lastChar == 'a' || lastChar == 'i'
      ){
          return true; 
      }
  return false;
}

Nhìn cũng ổn đấy, mỗi tội đoạn điều kiện kia nhìn đau mắt quá!!! Phải clean code thôi.
leetcode-2586-3

5. Clean code rất bổ não và tốt cho mắt

Các bạn đọc bài viết của mình sẽ thấy mình hay nhắc tới việc chia nhỏ module ra để dễ quản lý cũng như dễ bảo trì, fix bug sau này. Bên cạnh đó việc chia nhỏ công việc ra sẽ tránh được việc code của bạn bị lặp đi lặp lại một cách không cần thiết. Ví dụ như đoạn này:

if(firstChar == 'u' || firstChar == 'e' || firstChar == 'o' || firstChar == 'a' || firstChar == 'i'
&& lastChar == 'u' || lastChar == 'e' || lastChar == 'o' || lastChar == 'a' || lastChar == 'i'){
             return true; 
}

Với đoạn code vô duyên này tôi sẽ tạo thêm 1 function khác để làm riêng công việc check nguyên âm:

public static boolean checkVowel(char ch){
  return ch == 'u' || ch == 'e' || ch == 'o' || ch == 'a' || ch == 'i';
}

Nhờ có function này, việc tôi làm bây giờ chỉ là đưa kí tự vào check là xong. Code cuối cùng của chúng ta sẽ là:

public static int vowelStrings(String[] words, int left, int right) {
  int count = 0;

  for (int i = left; i <= right; i++) {
      if (checkWord(words[i])) {
          count++;
      }
  }
  return count;
}

public static boolean checkWord(String str){
  char firstChar = str.charAt(0);
  char lastChar = str.charAt(str.length() - 1);
  return checkVowel(firstChar) && checkVowel(lastChar);
}

public static boolean checkVowel(char ch){
  return ch == 'u' || ch == 'e' || ch == 'o' || ch == 'a' || ch == 'i';
}

Nhìn ổn hơn rất nhiều đấy, các bạn chia công việc thành các module nhỏ hơn như vậy thì sau này rất dễ fix bug, bảo trì cũng như tốt hơn trong việc tư duy.

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!!!