Valid Anagram: hai chuỗi có cùng bộ chữ cái không

Cho hai chuỗi s và t chỉ gồm chữ thường a đến z. Trả về true nếu t là anagram của s, tức là dùng đúng các chữ cái của s, mỗi chữ đúng số lần, chỉ khác thứ tự.

Đầu vào: s = "anagram", t = "nagaram"
Đầu ra:  true

Đầu vào: s = "rat", t = "car"
Đầu ra:  false

Trong game: trò chơi xếp chữ phát cho người chơi một bộ ô chữ. Khi người chơi nộp một từ, game kiểm tra từ đó có dùng đúng bộ ô được phát không.

Cách dễ nghĩ: sắp xếp rồi so

Hai chuỗi là anagram khi và chỉ khi sắp xếp các chữ cái xong thì giống hệt nhau. "rat" thành "art", "tar" cũng thành "art".

bool IsAnagram(string s, string t)
{
    char[] a = s.ToCharArray();
    char[] b = t.ToCharArray();
    Array.Sort(a);
    Array.Sort(b);
    return new string(a) == new string(b);
}

def is_anagram(s, t):
    return sorted(s) == sorted(t)

Độ phức tạp: thời gian O(n log n) vì phải sắp xếp, bộ nhớ O(n) cho hai bản sao. Code ngắn, dễ đọc, nhưng vẫn làm thừa việc: ta chỉ cần biết mỗi chữ xuất hiện mấy lần, không cần biết thứ tự.

Cách nhanh: đếm từng chữ cái

Tạo một mảng 26 ô, mỗi ô ứng với một chữ cái. Đi qua s thì cộng, đi qua t thì trừ. Cuối cùng mọi ô đều bằng 0 thì hai chuỗi là anagram.

Vị trí của chữ c trong mảng là c - 'a': chữ a ở ô 0, chữ b ở ô 1, chữ z ở ô 25. Python dùng ord(c) - ord("a") cho việc này.

bool IsAnagram(string s, string t)
{
    if (s.Length != t.Length) return false;
    var counts = new int[26];
    for (int i = 0; i < s.Length; i++)
    {
        counts[s[i] - 'a']++;
        counts[t[i] - 'a']--;
    }
    foreach (int c in counts)
        if (c != 0) return false;
    return true;
}

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for a, b in zip(s, t):
        counts[ord(a) - ord("a")] += 1
        counts[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in counts)

Chạy tay với s = "rat", t = "tar" (chỉ ghi các ô khác 0):

Kết quả true. Độ phức tạp: thời gian O(n), bộ nhớ O(1) vì mảng luôn có 26 ô, không phụ thuộc độ dài chuỗi.

Python có sẵn collections.Counter để đếm, viết gọn thành Counter(s) == Counter(t). Trong phỏng vấn vẫn nên biết cách tự đếm như trên.

Lỗi hay gặp: dùng c - 'a' khi chuỗi có chữ hoa, dấu cách hay chữ tiếng Việt. Chữ 'A' cho ra số âm, chữ 'ă' cho ra số lớn hơn 25, và chương trình văng IndexOutOfRangeException (C#) hoặc IndexError (Python). Nếu đề không hứa chỉ có a đến z, hãy dùng Dictionary<char, int> hoặc dict để đếm.

Khi đi phỏng vấn

• Hỏi ngay: chuỗi chỉ có chữ thường tiếng Anh, hay có cả Unicode? Câu trả lời quyết định dùng mảng 26 ô hay bảng băm.
• Kiểm tra độ dài trước tiên. Khác độ dài là trả về false luôn, vừa nhanh vừa tránh lỗi khi duyệt song song hai chuỗi.

Bài tập

Trong game chế tạo đồ, mỗi nguyên liệu là một chữ cái. recipe là các nguyên liệu cần, bag là nguyên liệu đang có. Trả về true nếu đủ nguyên liệu để chế, mỗi nguyên liệu chỉ dùng một lần. Hai chuỗi chỉ gồm chữ thường a đến z.

Đầu vào: recipe = "aab", bag = "baa"
Đầu ra:  true

Đầu vào: recipe = "aa", bag = "ab"
Đầu ra:  false

bool CanCraft(string recipe, string bag)
{
    var counts = new int[26];
    foreach (char c in bag) counts[c - 'a']++;
    foreach (char c in recipe)
    {
        counts[c - 'a']--;
        if (counts[c - 'a'] < 0) return false;
    }
    return true;
}

def can_craft(recipe, bag):
    counts = [0] * 26
    for c in bag:
        counts[ord(c) - ord("a")] += 1
    for c in recipe:
        counts[ord(c) - ord("a")] -= 1
        if counts[ord(c) - ord("a")] < 0:
            return False
    return True