- vừa được xem lúc

Bài toán Valid Anagram - Kiểm tra chuỗi anagram

0 0 6

Người đăng: Nguyễn Ánh Dung

Theo Viblo Asia

Anagram là gì?

Một chuỗi được gọi là anagram của chuỗi khác nếu chúng chứa cùng tập hợp các ký tự (bao gồm chữ cái, số, hoặc ký tự đặc biệt) với số lần xuất hiện giống nhau, nhưng thứ tự các ký tự có thể khác nhau.

Ví dụ, "listen" và "silent" là anagram vì chúng có cùng các ký tự (l, i, s, t, e, n) với tần suất giống nhau, dù sắp xếp khác nhau.

Định nghĩa bài toán

Cho hai chuỗi s và t, hãy kiểm tra xem t có phải là anagram của s hay không. Hai chuỗi là anagram nếu chúng có cùng các ký tự với tần suất xuất hiện giống nhau, không phân biệt thứ tự. Một số biến thể có thể yêu cầu bỏ qua chữ hoa/thường hoặc ký tự đặc biệt.

Ví dụ:

s = "anagram", t = "nagaram" → Hợp lệ (là anagram).

s = "rat", t = "car" → Không hợp lệ.

s = "a", t = "a" → Hợp lệ.

s = "ab", t = "a" → Không hợp lệ.

s = "Silent", t = "Listen" → Hợp lệ (nếu bỏ qua chữ hoa/thường).

Ràng buộc:

Chuỗi chỉ chứa chữ cái (hoặc chữ cái và số, tùy biến thể).

Độ dài chuỗi có thể từ 0 đến 10^5.

Một số biến thể yêu cầu bỏ qua chữ hoa/thường hoặc ký tự đặc biệt.

Các cách tiếp cận giải quyết

Bài toán này có thể được giải bằng nhiều phương pháp, từ đơn giản đến tối ưu hóa, sử dụng các cấu trúc dữ liệu như mảng, hash map, hoặc sắp xếp. Dưới đây là các cách tiếp cận phổ biến:

1. Sử dụng sắp xếp (Sorting)

Sắp xếp cả hai chuỗi và so sánh chúng để kiểm tra xem chúng có giống nhau hay không.

Thuật toán:

Kiểm tra độ dài của s và t. Nếu khác nhau, trả về False.

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

So sánh chuỗi đã sắp xếp. Nếu giống nhau, trả về True, ngược lại trả về False.

def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False return sorted(s) == sorted(t) 

Ưu điểm: Đơn giản, dễ triển khai, không cần cấu trúc dữ liệu phức tạp.

Nhược điểm: Tốn thời gian do sắp xếp, không tối ưu cho chuỗi dài.

Độ phức tạp:

Thời gian: O(n log n) (do sắp xếp).

Không gian: O(n) (tùy thuộc vào thuật toán sắp xếp hoặc nếu cần tạo bản sao chuỗi).

2. Sử dụng Hash Map (Dictionary)

Đếm tần suất xuất hiện của từng ký tự trong cả hai chuỗi bằng hash map.

Thuật toán:

Kiểm tra độ dài của s và t. Nếu khác nhau, trả về False.

Tạo một hash map để đếm tần suất ký tự trong s.

Giảm tần suất tương ứng khi duyệt t. Nếu ký tự không có trong hash map hoặc tần suất âm, trả về False.

Kiểm tra hash map xem tất cả tần suất có bằng 0 hay không.

def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False char_count = {} for char in s: char_count[char] = char_count.get(char, 0) + 1 for char in t: if char not in char_count: return False char_count[char] -= 1 if char_count[char] == 0: del char_count[char] return len(char_count) == 0

Ưu điểm: Hiệu quả về thời gian, dễ mở rộng cho các biến thể (ví dụ: bỏ qua chữ hoa/thường).

Nhược điểm: Tốn bộ nhớ phụ cho hash map.

Độ phức tạp:

Thời gian: O(n) (duyệt mỗi chuỗi một lần).

Không gian: O(k) (k là số ký tự khác nhau, tối đa 26 nếu chỉ có chữ cái thường).

3. Sử dụng mảng tần suất (Frequency Array)

Sử dụng một mảng cố định để đếm tần suất ký tự, thay vì hash map, khi chuỗi chỉ chứa chữ cái.

Thuật toán:

Kiểm tra độ dài của s và t. Nếu khác nhau, trả về False.

Tạo mảng 26 phần tử (cho chữ cái thường) để đếm tần suất.

Duyệt s, tăng tần suất cho mỗi ký tự.

Duyệt t, giảm tần suất tương ứng. Nếu tần suất âm, trả về False.

Kiểm tra mảng tần suất có toàn 0 hay không.

def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False freq = [0] * 26 for i in range(len(s)): freq[ord(s[i].lower()) - ord('a')] += 1 freq[ord(t[i].lower()) - ord('a')] -= 1 for count in freq: if count != 0: return False return True

Ưu điểm: Tối ưu bộ nhớ khi số ký tự giới hạn (ví dụ: chỉ chữ cái), nhanh hơn hash map trong trường hợp này.

Nhược điểm: Chỉ áp dụng được khi tập ký tự nhỏ (như chữ cái), không linh hoạt với ký tự đặc biệt.

Độ phức tạp:

Thời gian: O(n) (duyệt chuỗi một lần).

Không gian: O(1) (mảng kích thước cố định 26).

4. Sử dụng XOR (Biến thể sáng tạo)

Nếu chuỗi chỉ chứa các ký tự có giá trị ASCII, có thể dùng phép XOR để kiểm tra tính anagram (ít phổ biến).

Thuật toán:

Kiểm tra độ dài của s và t. Nếu khác nhau, trả về False.

Thực hiện XOR giá trị ASCII của tất cả ký tự trong s và t.

Nếu kết quả XOR bằng 0, hai chuỗi là anagram.

def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False xor_result = 0 for i in range(len(s)): xor_result ^= ord(s[i]) ^ ord(t[i]) return xor_result == 0

Ưu điểm: Ý tưởng sáng tạo, thể hiện hiểu biết về bitwise operation.

Nhược điểm: Không thực tế vì dễ bị lỗi với chuỗi dài hoặc tần suất ký tự khác nhau, khó mở rộng.

Độ phức tạp:

Thời gian: O(n).

Không gian: O(1).

Ứng dụng thực tế

Xử lý văn bản: Kiểm tra anagram được dùng trong tìm kiếm từ đồng nghĩa, phân tích văn bản, hoặc trò chơi chữ (như Scrabble, Wordle).

Mã hóa và bảo mật: So sánh chuỗi trong các thuật toán mã hóa hoặc kiểm tra tính toàn vẹn dữ liệu.

Giáo dục và phỏng vấn: Kiểm tra khả năng tư duy thuật toán, sử dụng cấu trúc dữ liệu như hash map hoặc mảng.

Trò chơi logic: Dùng trong các ứng dụng như tìm từ anagram trong ô chữ hoặc trò chơi ghép chữ.

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 60

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 184

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 69

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 102

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 64

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 61