Remove Vowels

Q: Độ phức tạp thời gian của việc loại bỏ nguyên âm là bao nhiêu?

Một lượt duyệt có độ phức tạp thời gian O(n) , vì mỗi ký tự được kiểm tra có phải nguyên âm hay không trong thời gian hằng số. Trong trường hợp xấu nhất, khi s hoàn toàn không có nguyên âm, kết quả đầu ra cần O(n) bộ nhớ. Gọi replace một lần cho mỗi nguyên âm cũng có độ phức tạp O(n) , nhưng cách này đọc chuỗi mười lần.

Q: Bạn có thể xóa các nguyên âm bằng biểu thức chính quy không?

Có. Thay mẫu [aeiouAEIOU] bằng chuỗi rỗng sẽ làm được việc đó chỉ trong một lần gọi ở hầu hết các ngôn ngữ. Cách này chạy trong O(n) , giống như vòng lặp, nhưng người phỏng vấn thường yêu cầu bạn viết vòng lặp để họ thấy cách bạn kiểm tra nguyên âm và tạo kết quả.

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

+10

Bạn nhận được một chuỗi s gồm các chữ cái tiếng Anh. Hãy trả về chuỗi thu được sau khi xóa mọi nguyên âm. Các nguyên âm là a, e, i, o và u, ở dạng chữ thường hoặc chữ hoa; trong bài này, y không phải là nguyên âm. Các chữ cái còn lại giữ nguyên thứ tự và kiểu chữ.

Hàm

removeVowels(s: string) → string

sstring: chuỗi chữ cái tiếng Anh cần làm sạch
Trả vềstring: s với mọi nguyên âm bị loại bỏ và các chữ cái còn lại giữ nguyên thứ tự ban đầu

Ràng buộc

1 ≤ s.length ≤ 3 × 10⁴
s chỉ chứa các chữ cái tiếng Anh (a đến z, A đến Z).
s chứa ít nhất một chữ cái không phải nguyên âm, vì vậy câu trả lời không bao giờ trống.

Ví dụ

Đầu vào: s = "Interview"
Đầu ra: "ntrvw"
Giải thích: Xóa I, e, i và e khỏi Interview sẽ còn lại n, t, r, v, w theo thứ tự đó. Chữ I viết hoa cũng là nguyên âm, nên hãy xóa nó.

Đầu vào: s = "rhythm"
Đầu ra: "rhythm"
Giải thích: rhythm không có a, e, i, o hay u, nên không có gì bị xóa. y không nằm trong danh sách nguyên âm nên vẫn được giữ lại.

Đầu vào: s = "EuropeanUnion"
Đầu ra: "rpnnn"
Giải thích: Tám trong số mười ba chữ cái của EuropeanUnion là nguyên âm, bao gồm cả chữ in hoa E và U. Năm phụ âm còn lại, r, p, n, n, n, giữ nguyên thứ tự và ghép lại thành rpnnn.

Câu hỏi mở rộng

Bạn nghĩ sao nếu chuỗi có thể chứa bất kỳ chữ cái Unicode nào, chẳng hạn như É hoặc ö? Chữ nào trong số đó là nguyên âm, và bạn cần thay đổi phép kiểm tra 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

Xóa từng ký tự một khỏi giữa chuỗi sẽ làm mọi thứ phía sau mỗi chỗ trống dịch chuyển. Thay vào đó, hãy tạo câu trả lời bằng cách duyệt chuỗi một lần và sao chép mọi chữ cái không phải nguyên âm. Xử lý đúng các nguyên âm viết hoa, rồi ghép kết quả vào một bộ dựng.

Xóa từng nguyên âm bằng một lượt riêng

Ý tưởng

Hầu hết các ngôn ngữ xóa mọi bản sao của một ký tự trong một lần gọi: thay ký tự đó bằng không có gì. Làm vậy một lần cho từng ký tự trong a e i o u A E I O U. Các phụ âm không bao giờ bị đụng đến, nên chúng giữ nguyên thứ tự và kiểu chữ. Với Interview, các lượt xử lý cho e, i và I cho kết quả lần lượt là Intrviw, Intrvw và ntrvw; bảy ký tự còn lại không tìm thấy gì.

Mỗi lượt xử lý đọc toàn bộ chuỗi, tổng cộng khoảng 10n bước. Độ phức tạp vẫn là O(n), nhưng với 3 × 10^4 chữ cái thì cần 3 × 10^5 bước, trong khi chỉ cần 3 × 10^4 bước cho một lượt duyệt.

Thuật toán

Lấy lần lượt từng chữ cái nguyên âm trong số mười chữ cái aeiouAEIOU.
Với mỗi chữ cái, thay mọi bản sao của nó trong s bằng chuỗi rỗng.
Sau mười lượt, trả về phần còn lại của s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

Một lượt giữ nguyên các phụ âm

Ý tưởng

Hãy thu thập những gì còn lại thay vì xóa những gì cần bỏ. Duyệt qua s một lần và nối thêm từng ký tự không thuộc một trong mười chữ cái nguyên âm. Bạn nối thêm theo thứ tự đọc và không bao giờ thay đổi ký tự nào, vì vậy các phụ âm vẫn giữ nguyên thứ tự và chữ hoa, chữ thường.

Mỗi ký tự cần một phép kiểm tra có thời gian hằng số (tra cứu trong tập hợp, dùng switch hoặc tìm kiếm trong chuỗi gồm mười chữ cái), vì vậy thời gian là O(n). Nối thêm vào bộ dựng chuỗi hoặc danh sách, rồi chuyển thành chuỗi một lần ở cuối. Bản thân đầu ra chiếm O(n) không gian.

Thuật toán

Bắt đầu bằng một bộ dựng rỗng để tạo kết quả.
Duyệt qua s từng ký tự một.
Nếu ký tự không thuộc aeiouAEIOU, hãy thêm ký tự đó vào bộ dựng.
Trả về bộ dựng dưới dạng chuỗi.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

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

Quên các nguyên âm viết hoa. Chỉ kiểm tra aeiou sẽ biến Interview thành Intrvw thay vì ntrvw.
Chuyển cả chuỗi thành chữ thường để rút ngắn phần kiểm tra. Khi đó, QUEUEING sẽ thành qng thay vì QNG. Chỉ chuyển bản sao dùng để kiểm tra thành chữ thường.
Xóa phần tử khi duyệt xuôi theo chỉ số. Xóa s[i] sẽ đẩy chữ cái tiếp theo vào vị trí i, còn i++ lại bỏ qua chữ cái đó, nên aab sẽ thành ab.
Nối thêm vào một chuỗi bất biến bằng += trong vòng lặp. Trong Java hoặc C#, mỗi bước sẽ sao chép toàn bộ chuỗi, tốn khoảng 4.5 × 10^8 lượt sao chép ký tự cho 3 × 10^4 chữ cái.

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

Độ phức tạp thời gian của việc loại bỏ nguyên âm là bao nhiêu?

Một lượt duyệt có độ phức tạp thời gian O(n), vì mỗi ký tự được kiểm tra có phải nguyên âm hay không trong thời gian hằng số. Trong trường hợp xấu nhất, khi s hoàn toàn không có nguyên âm, kết quả đầu ra cần O(n) bộ nhớ. Gọi replace một lần cho mỗi nguyên âm cũng có độ phức tạp O(n), nhưng cách này đọc chuỗi mười lần.

Bạn có thể xóa các nguyên âm bằng biểu thức chính quy không?

Có. Thay mẫu [aeiouAEIOU] bằng chuỗi rỗng sẽ làm được việc đó chỉ trong một lần gọi ở hầu hết các ngôn ngữ. Cách này chạy trong O(n), giống như vòng lặp, nhưng người phỏng vấn thường yêu cầu bạn viết vòng lặp để họ thấy cách bạn kiểm tra nguyên âm và tạo kết quả.

Tại sao không xóa các nguyên âm khỏi chuỗi ngay tại chỗ?

Xóa một ký tự ở giữa sẽ làm mọi ký tự phía sau dịch sang trái, vì vậy xóa nhiều ký tự có thể tốn O(n²). Bạn có thể thực hiện ngay trên chuỗi trong O(n) bằng hai chỉ số, một chỉ số đọc từng ký tự và một chỉ số ghi ký tự tiếp theo cần giữ lại, nhưng trong hầu hết các ngôn ngữ, bạn không thể thay đổi chuỗi, nên tạo chuỗi mới là cách tự nhiên nhất.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "Interview"

Đầu ra mong đợi

"ntrvw"