Valid Anagram

Q: Độ phức tạp thời gian của Valid Anagram là bao nhiêu?

Đếm chữ cái mất thời gian O(n) và dùng thêm O(1) bộ nhớ, vì mảng đếm có 26 phần tử bất kể các chuỗi dài bao nhiêu. Sắp xếp cả hai chuỗi mất thời gian O(n log n) và thường dùng O(n) bộ nhớ cho các bản sao đã sắp xếp.

Q: Khi kiểm tra hai từ có phải là từ đảo chữ của nhau không, sắp xếp hay đếm sẽ tốt hơn?

Về lý thuyết, cách đếm nhanh hơn, O(n) so với O(n log n) , và có thể dừng ngay khi một chữ cái xuất hiện quá nhiều. Cách sắp xếp có mã ngắn hơn và dùng được với mọi bảng chữ cái mà không cần thay đổi. Trong buổi phỏng vấn, hãy trình bày cách sắp xếp trước, sau đó cải tiến thành cách đếm.

DễBăm Sắp xếp

+10

Hai chuỗi là từ đảo chữ của nhau khi một chuỗi được tạo bằng cách sắp xếp lại các ký tự trong chuỗi kia: chúng dùng cùng các chữ cái, mỗi chữ cái xuất hiện cùng số lần. Bạn nhận được hai chuỗi s và t chỉ gồm các chữ cái tiếng Anh viết thường. Trả về true nếu t là từ đảo chữ của s, nếu không thì trả về false.

Hàm

isAnagram(s: string, t: string) → boolean

sstring: chuỗi đầu tiên, chữ cái viết thường
tstring: chuỗi cần dùng để kiểm tra s
Trả vềboolean: đúng nếu t sử dụng chính xác các chữ cái của s, mỗi chữ cái xuất hiện cùng số lần

Ràng buộc

1 ≤ s.length, t.length ≤ 2 × 10⁴
s và t chỉ chứa các chữ cái tiếng Anh viết thường (a đến z).
Hai độ dài có thể khác nhau.

Ví dụ

Đầu vào: s = "listen"t = "silent"
Đầu ra: true
Giải thích: Cả hai từ đều chứa một chữ e, i, l, n, s và t, nên silent là listen với các chữ cái được sắp xếp lại.

Đầu vào: s = "aabb"t = "abbb"
Đầu ra: false
Giải thích: Độ dài khớp nhau và cả hai chỉ dùng a và b, nhưng aabb có hai ký tự a, còn abbb có một ký tự a, nên số lượng khác nhau.

Đầu vào: s = "cat"t = "cast"
Đầu ra: false
Giải thích: cast có bốn chữ cái còn cat có ba, nên không cách sắp xếp lại nào của cat có thể tạo thành từ đó.

Câu hỏi mở rộng

Nếu chuỗi có thể chứa mọi ký tự Unicode thay vì chỉ từ a đến z thì sao? Bạn sẽ thay đổi cách đếm 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

Chuỗi đảo chữ giữ nguyên số lượng từng ký tự nhưng bỏ qua thứ tự. Vì vậy, bạn cần một bản tóm tắt cho mỗi chuỗi, không nhớ vị trí các ký tự nhưng nhớ số lượng từng ký tự. Sắp xếp tạo bản tóm tắt đó trong O(n log n); bảng gồm 26 bộ đếm tạo bản tóm tắt chỉ trong một lượt duyệt.

Sắp xếp cả hai chuỗi

Ý tưởng

Sắp xếp đưa các chữ cái của chuỗi về thứ tự bảng chữ cái và xóa dấu vết vị trí ban đầu của từng chữ cái. listen và silent đều được sắp xếp thành eilnst; aabb và abbb giữ nguyên và khác nhau tại chỉ số 1. Hai chuỗi có cùng các chữ cái với số lần xuất hiện bằng nhau khi và chỉ khi dạng đã sắp xếp của chúng giống nhau.

Trước tiên, hãy so sánh độ dài và bỏ qua cả hai lần sắp xếp nếu chúng khác nhau. Sắp xếp tốn thời gian O(n log n) và, trong hầu hết các ngôn ngữ, tốn O(n) không gian để tạo bản sao các ký tự. Với n = 2 × 10^4, cách này nhanh, nhưng đếm sẽ ít tốn công hơn.

Thuật toán

Nếu độ dài của s và t khác nhau, hãy trả về false.
Sao chép các ký tự của mỗi chuỗi vào một mảng.
Sắp xếp cả hai mảng.
Trả về true nếu hai mảng đã sắp xếp bằng nhau, phần tử này so với phần tử kia.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Đếm từng chữ cái

Ý tưởng

Chỉ có 26 chữ cái có thể xuất hiện, nên hãy giữ một bộ đếm cho mỗi chữ cái trong một mảng gồm 26 phần tử, với chỉ số bằng mã ký tự trừ đi mã của a. Duyệt qua s, tăng bộ đếm của mỗi chữ cái thêm 1, rồi duyệt qua t, giảm bộ đếm đi 1.

Bộ đếm nhỏ hơn 0 có nghĩa là t dùng chữ cái đó nhiều hơn s, vì vậy bạn có thể dừng lại ngay. Với aabb và abbb, sau khi duyệt s, các bộ đếm lần lượt là a: 2, b: 2; chữ b thứ ba của t khiến bộ đếm b giảm xuống -1, và bạn trả về false.

Nếu không có bộ đếm nào âm, số lượng khớp nhau. Độ dài của hai chuỗi bằng nhau, nên sau khi duyệt cả hai chuỗi, tổng các bộ đếm bằng 0; nếu không có số âm, một số dương sẽ không có gì để cân bằng nó, vì vậy tất cả đều bằng 0. Đó là lý do kiểm tra độ dài là một phần của chứng minh, chứ không phải lối tắt.

Mỗi chuỗi được đọc một lần, thời gian O(n), và mảng chứa 26 số bất kể độ dài, dùng thêm O(1) không gian.

Thuật toán

Nếu độ dài của s và t khác nhau, trả về false.
Tạo một mảng gồm 26 số 0.
Với mỗi chữ cái trong s, tăng bộ đếm tương ứng thêm 1.
Với mỗi chữ cái trong t, giảm bộ đếm tương ứng đi 1; nếu giá trị giảm xuống dưới 0, trả về false.
Trả về true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

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

So sánh các tập hợp chữ cái. aabb và abbb đều chỉ dùng chính xác a và b, nhưng chúng không phải là từ đảo chữ.
Kiểm tra xem mỗi chữ cái trong t có xuất hiện ở đâu đó trong s hay không mà không gạch bỏ chữ cái đó. aab và abb đều vượt qua phép kiểm tra này theo cả hai chiều.
Bỏ qua bước kiểm tra độ dài trong phiên bản đếm. Với s = ab và t = a, không bộ đếm nào giảm xuống dưới 0, nên code trả về true một cách sai lệch.
Dùng mã ký tự thô để lấy chỉ số trong mảng bộ đếm. a có mã 97, vượt xa giới hạn của mảng có 26 phần tử; trước tiên hãy trừ mã của a, còn trong Lua và R thì cộng thêm 1 vì mảng của chúng bắt đầu từ 1.

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

Độ phức tạp thời gian của Valid Anagram là bao nhiêu?

Đếm chữ cái mất thời gian O(n) và dùng thêm O(1) bộ nhớ, vì mảng đếm có 26 phần tử bất kể các chuỗi dài bao nhiêu. Sắp xếp cả hai chuỗi mất thời gian O(n log n) và thường dùng O(n) bộ nhớ cho các bản sao đã sắp xếp.

Khi kiểm tra hai từ có phải là từ đảo chữ của nhau không, sắp xếp hay đếm sẽ tốt hơn?

Về lý thuyết, cách đếm nhanh hơn, O(n) so với O(n log n), và có thể dừng ngay khi một chữ cái xuất hiện quá nhiều. Cách sắp xếp có mã ngắn hơn và dùng được với mọi bảng chữ cái mà không cần thay đổi. Trong buổi phỏng vấn, hãy trình bày cách sắp xếp trước, sau đó cải tiến thành cách đếm.

Tại sao nên dùng một mảng đếm thay vì hai mảng?

Dùng hai mảng, mỗi chuỗi một mảng, cũng được: đếm từng chuỗi, rồi so sánh các mảng. Dùng một mảng tăng dần với s và giảm dần với t sẽ chỉ tốn một nửa bộ nhớ, đồng thời cho phép bạn trả về false ngay khi một bộ đếm âm, không cần vòng lặp so sánh cuối cùng.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "listen"
t = "silent"

Đầu ra mong đợi

true