Count a Character

Q: Bạn có thể dùng hàm đếm tích hợp sẵn trong buổi phỏng vấn không?

Thường là có, miễn là bạn có thể nêu được độ phức tạp. str.count và các hàm tương tự trong Python vẫn đọc toàn bộ chuỗi, nên có độ phức tạp O(n) . Hãy sẵn sàng viết vòng lặp nếu người phỏng vấn yêu cầu.

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

+10

Bạn nhận được một chuỗi s và một ký tự c. Hãy trả về số lần c xuất hiện trong s. Kết quả phân biệt chữ hoa và chữ thường: B và b là hai ký tự khác nhau.

Hàm

countChar(s: string, c: string) → integer

sstring: chuỗi chữ cái tiếng Anh cần tìm
cstring: một chữ cái cần đếm
Trả vềinteger: có bao nhiêu ký tự trong s bằng c

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, từ A đến Z).
c chính xác là một chữ cái tiếng Anh.

Ví dụ

Đầu vào: s = "Mississippi"c = "s"
Đầu ra: 4
Giải thích: Mississippi có s ở các chỉ số 2, 3, 5 và 6, nên đáp án là 4.

Đầu vào: s = "Banana"c = "b"
Đầu ra: 0
Giải thích: Banana bắt đầu bằng chữ B viết hoa, còn bạn đang tìm chữ b viết thường. Không có kết quả nào khớp, nên đáp án là 0.

Câu hỏi mở rộng

Nếu c có thể là một từ gồm nhiều chữ cái, chẳng hạn như ss, thì sao? Các kết quả khớp chồng lấn có được tính không, và vòng lặp của bạn sẽ thay đổi như thế nào?

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

Mỗi ký tự trong s có thể là c, vì vậy bạn xem từng ký tự một lần và đếm số ký tự khớp. Hãy chú ý đến chữ hoa chữ thường: chữ hoa là một ký tự khác.

Xóa mọi c và so sánh độ dài

Ý tưởng

Tạo một bản sao của s, trong đó đã xóa mọi c. Mỗi lần xóa làm bản sao ngắn đi một ký tự, nên độ dài chênh lệch chính là số lần xóa. Với Mississippi, bản sao là Miiippi: 11 trừ 7 bằng 4.

Thời gian chạy là O(n), nhưng bản sao cần thêm O(n) bộ nhớ, còn biến đếm thì không cần.

Thuật toán

Tạo một bản sao của s, bỏ qua mọi ký tự bằng c.
Đo độ dài của s và độ dài của bản sao.
Trả về độ dài của s trừ đi độ dài của bản sao.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Một lượt với bộ đếm

Ý tưởng

Đếm khi đọc thay vì tạo một bản sao. Bộ đếm bắt đầu từ 0 và tăng thêm 1 cho mỗi ký tự bằng c. Phép so sánh bằng thông thường khiến chữ hoa không khớp với chữ thường.

Mỗi ký tự chỉ được so sánh một lần và chỉ lưu bộ đếm: thời gian O(n), bộ nhớ O(1). Không có lời giải nào nhanh hơn O(n), vì ký tự bạn bỏ qua có thể là một chữ c nữa.

Thuật toán

Đọc chữ cái mục tiêu từ c và đặt count = 0.
Duyệt qua s, mỗi lần một ký tự.
Nếu ký tự trùng với ký tự mục tiêu, tăng count thêm 1.
Trả về count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

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

Bỏ qua chữ hoa và chữ thường. Chuyển cả hai phía thành chữ thường khiến Banana và b trả về 1, nhưng đáp án là 0.
So sánh một ký tự với một chuỗi. Trong Java, C, C++, C# và Go, c là một chuỗi, còn s[i] hoặc s.charAt(i) là một ký tự. Lấy c[0] (hoặc c.charAt(0)) một lần trước vòng lặp.
So sánh chuỗi bằng == trong Java. String.valueOf(s.charAt(i)) == c so sánh danh tính đối tượng và hầu như luôn trả về false. Hãy so sánh các giá trị char.
Gọi strlen(s) trong điều kiện vòng lặp ở C. Hàm này quét lại chuỗi ở mỗi bước, vì vậy 5 × 10^4 ký tự tốn khoảng 2.5 × 10^9 bước.

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

Làm thế nào để đếm số lần xuất hiện của một ký tự (character) trong chuỗi (string)?

Duyệt chuỗi một lần bằng bộ đếm bắt đầu từ 0, rồi tăng thêm 1 mỗi khi ký tự hiện tại trùng với ký tự bạn muốn đếm. Cách này mất thời gian O(n) và dùng thêm O(1) bộ nhớ. Để đếm không phân biệt chữ hoa chữ thường, trước tiên hãy chuyển cả chuỗi và ký tự thành chữ thường.

Bạn có thể dùng hàm đếm tích hợp sẵn trong buổi phỏng vấn không?

Thường là có, miễn là bạn có thể nêu được độ phức tạp. str.count và các hàm tương tự trong Python vẫn đọc toàn bộ chuỗi, nên có độ phức tạp O(n). Hãy sẵn sàng viết vòng lặp nếu người phỏng vấn yêu cầu.

Làm thế nào để đếm tất cả ký tự cùng một lúc?

Duyệt qua một lần và đếm số lần xuất hiện của từng ký tự bằng một hash map hoặc một mảng gồm 52 bộ đếm cho các chữ cái tiếng Anh. Sau lượt duyệt đó, bạn chỉ cần tra cứu một lần để biết số lần xuất hiện của bất kỳ chữ cái nào. Dùng cách này khi bạn cần đếm nhiều chữ cái trong cùng một chuỗi.

def countChar(s, c):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

s = "Mississippi"
c = "s"

Đầu ra mong đợi