Count Vowels

Q: Độ phức tạp thời gian của việc đếm nguyên âm là gì?

O(n) , trong đó n là độ dài của chuỗi, vì mỗi ký tự được kiểm tra một lần với tối đa năm chữ cái. Bộ nhớ phụ cần dùng là O(1) : một biến đếm và tập nguyên âm cố định.

Q: Trong bài toán này, y có phải là một nguyên âm không?

Không. Trong chính tả tiếng Anh, y đôi khi đóng vai trò là nguyên âm, như trong từ rhythm , nhưng các bài toán lập trình hầu như luôn định nghĩa nguyên âm là a , e , i , o và u , và bài này cũng vậy. Nếu bài toán có y , hãy thêm chữ cái đó vào những chữ cái bạn kiểm tra.

Người mớiMảng và chuỗi

+10

Cho chuỗi s gồm các chữ cái tiếng Anh, hãy trả về số ký tự nguyên âm trong chuỗi. Các nguyên âm gồm a, e, i, o và u, dù viết thường hay viết hoa. Chữ cái y không được tính.

Hàm

countVowels(s: string) → integer

sstring: chuỗi chữ cái tiếng Anh cần quét
Trả vềinteger: số nguyên âm trong s, tính cả chữ hoa lẫn chữ thường

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh từ a đến z và từ A đến Z.

Ví dụ

Đầu vào: s = "Interview"
Đầu ra: 4
Giải thích: Các nguyên âm là I, e, i và e. Chữ I viết hoa được tính như chữ viết thường, vì vậy đáp án là 4.

Đầu vào: s = "rhythm"
Đầu ra: 0
Giải thích: rhythm không có a, e, i, o hay u, và y không nằm trong danh sách, vì vậy đáp án là 0.

Câu hỏi mở rộng

Bạn có thể trả về số lần xuất hiện của mỗi nguyên âm trong năm nguyên âm mà vẫn chỉ đọc chuỗi một lần không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Đọc chuỗi một lần bằng bộ đếm. Chuyển từng ký tự thành chữ thường, như vậy chỉ cần kiểm tra một lần với năm nguyên âm là bao quát được cả chữ hoa lẫn chữ thường.

Đếm từng nguyên âm bằng một lượt duyệt riêng

Ý tưởng

Đếm từng chữ cái trong số mười chữ cái thuộc aeiouAEIOU bằng một lượt duyệt riêng qua chuỗi, rồi cộng mười số đếm lại. Mỗi nguyên âm đều trùng khớp chính xác với một trong mười chữ cái, nên được đếm một lần, và không có phụ âm nào trùng khớp với chúng.

Chuỗi được đọc mười lần. Độ phức tạp vẫn là O(n), nhưng với 5 × 10^4 ký tự, cách này cần 5 × 10^5 phép so sánh, trong khi một lượt duyệt chỉ đọc mỗi ký tự một lần.

Thuật toán

Đặt total = 0.
Lấy từng chữ cái trong mười chữ cái aeiouAEIOU.
Với mỗi chữ cái, duyệt toàn bộ chuỗi và cộng 1 vào total mỗi khi một ký tự bằng chữ cái đó.
Sau mười lượt duyệt, trả về total.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

Một lượt duyệt với kiểm tra chữ thường

Ý tưởng

Đọc chuỗi một lần và kiểm tra xem mỗi ký tự có phải là nguyên âm không. Chuyển chuỗi thành chữ thường trước sẽ biến I thành i và giữ nguyên các phụ âm, nên bạn chỉ cần so sánh với năm chữ cái thay vì mười.

Việc kiểm tra mất thời gian hằng số: dùng switch, tra cứu trong tập hợp hoặc tìm kiếm trong chuỗi aeiou. Mỗi ký tự chỉ được đọc một lần và chỉ cần lưu một biến đếm: thời gian O(n), bộ nhớ O(1).

Thuật toán

Đặt count = 0.
Duyệt chuỗi từng ký tự một.
Chuyển ký tự thành chữ thường.
Nếu ký tự đó là a, e, i, o hoặc u, hãy cộng 1 vào count.
Trả về count.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

Lỗi thường gặp và trường hợp biên

Chỉ kiểm tra chữ thường. Chỉ so sánh với aeiou sẽ bỏ sót chữ I viết hoa trong Interview và trả về 3.
Đếm y. Ở đây, y không bao giờ là nguyên âm, nên rhythm cho kết quả 0.
Coi chỉ số 0 là không khớp. "aeiou".indexOf('a') trả về 0, tức là có khớp. Hãy kiểm tra giá trị -1, hoặc trong PHP, so sánh strpos với false bằng !==, vì trong PHP 0 == false.
Gọi strlen(s) trong điều kiện của vòng lặp trong C. Hàm này quét lại chuỗi ở mỗi bước, nên xử lý 5 × 10^4 ký tự sẽ tốn khoảng 2.5 × 10^9 bước.

Câu hỏi thường gặp3

Bạn đếm số nguyên âm trong một chuỗi như thế nào?

Duyệt qua chuỗi một lần bằng bộ đếm. Chuyển từng ký tự thành chữ thường và cộng thêm 1 nếu đó là a, e, i, o hoặc u. Khi vòng lặp kết thúc, bộ đếm sẽ chứa đáp án.

Độ phức tạp thời gian của việc đếm nguyên âm là gì?

O(n), trong đó n là độ dài của chuỗi, vì mỗi ký tự được kiểm tra một lần với tối đa năm chữ cái. Bộ nhớ phụ cần dùng là O(1): một biến đếm và tập nguyên âm cố định.

Trong bài toán này, y có phải là một nguyên âm không?

Không. Trong chính tả tiếng Anh, y đôi khi đóng vai trò là nguyên âm, như trong từ rhythm, nhưng các bài toán lập trình hầu như luôn định nghĩa nguyên âm là a, e, i, o và u, và bài này cũng vậy. Nếu bài toán có y, hãy thêm chữ cái đó vào những chữ cái bạn kiểm tra.

def countVowels(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

s = "Interview"

Đầu ra mong đợi