Kiểm tra xem hai chuỗi có phải là đảo ngữ trong Java không

1. Khái quát chung

Theo Wikipedia, đảo ngữ là một từ hoặc cụm từ được hình thành bằng cách sắp xếp lại các chữ cái của một từ hoặc cụm từ khác nhau.

Chúng ta có thể khái quát điều này trong xử lý chuỗi bằng cách nói rằng một chuỗi đảo chữ là một chuỗi khác với số lượng chính xác của mỗi ký tự trong đó, theo bất kỳ thứ tự nào .

Trong hướng dẫn này, chúng ta sẽ xem xét việc phát hiện toàn bộ chuỗi đảo chữ trong đó số lượng của mỗi ký tự phải bằng nhau, bao gồm các ký tự không phải alpha như dấu cách và chữ số. Ví dụ: “! Low-salt!” "owls-lat !!" sẽ được coi là đảo ngữ vì chúng chứa các ký tự giống hệt nhau.

2. Giải pháp

Hãy so sánh một vài giải pháp có thể quyết định xem hai chuỗi có phải là đảo ngữ hay không. Mỗi giải pháp sẽ kiểm tra ngay từ đầu xem hai chuỗi có cùng số ký tự hay không. Đây là một cách nhanh chóng để thoát sớm vì các đầu vào có độ dài khác nhau không thể là từ đảo ngữ .

Đối với mỗi giải pháp khả thi, chúng ta hãy xem xét độ phức tạp triển khai đối với chúng tôi với tư cách là nhà phát triển. Chúng tôi cũng sẽ xem xét độ phức tạp về thời gian của CPU, sử dụng ký hiệu O lớn.

3. Kiểm tra bằng cách sắp xếp

Chúng ta có thể sắp xếp lại các ký tự của mỗi chuỗi bằng cách sắp xếp các ký tự của chúng, điều này sẽ tạo ra hai mảng ký tự được chuẩn hóa.

Nếu hai chuỗi là từ đảo ngữ, thì các dạng chuẩn hóa của chúng phải giống nhau.

Trong Java, trước tiên chúng ta có thể chuyển đổi hai chuỗi thành mảng char [] . Sau đó, chúng ta có thể sắp xếp hai mảng này và kiểm tra sự bằng nhau:

boolean isAnagramSort(String string1, String string2) { if (string1.length() != string2.length()) { return false; } char[] a1 = string1.toCharArray(); char[] a2 = string2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); } 

Giải pháp này rất dễ hiểu và dễ thực hiện. Tuy nhiên, thời gian chạy tổng thể của thuật toán này là O (n log n) bởi vì sắp xếp một mảng n ký tự sẽ mất O (n log n) thời gian.

Để thuật toán hoạt động, nó phải tạo bản sao của cả hai chuỗi đầu vào dưới dạng mảng ký tự, sử dụng thêm một ít bộ nhớ.

4. Kiểm tra bằng cách đếm

Một chiến lược thay thế là đếm số lần xuất hiện của mỗi ký tự trong đầu vào của chúng tôi. Nếu các biểu đồ này bằng nhau giữa các đầu vào, thì các chuỗi là ký tự đảo ngữ.

Để tiết kiệm một ít bộ nhớ, hãy chỉ xây dựng một biểu đồ. Chúng tôi sẽ tăng số lượng cho mỗi ký tự trong chuỗi đầu tiên và giảm số lượng cho mỗi ký tự trong chuỗi thứ hai. Nếu hai chuỗi là đảo ngữ, thì kết quả sẽ là mọi thứ cân bằng bằng 0.

Biểu đồ cần một bảng số lượng có kích thước cố định với kích thước được xác định bởi kích thước tập ký tự. Ví dụ: nếu chúng ta chỉ sử dụng một byte để lưu trữ mỗi ký tự, thì chúng ta có thể sử dụng kích thước mảng đếm là 256 để đếm sự xuất hiện của mỗi ký tự:

private static int CHARACTER_RANGE= 256; public boolean isAnagramCounting(String string1, String string2) { if (string1.length() != string2.length()) { return false; } int count[] = new int[CHARACTER_RANGE]; for (int i = 0; i < string1.length(); i++) { count[string1.charAt(i)]++; count[string2.charAt(i)]--; } for (int i = 0; i < CHARACTER_RANGE; i++) { if (count[i] != 0) { return false; } } return true; }

Giải pháp này nhanh hơn với độ phức tạp thời gian là O (n) . Tuy nhiên, nó cần thêm không gian cho mảng đếm. Ở 256 số nguyên, đối với ASCII, điều đó không quá tệ.

Tuy nhiên, nếu chúng ta cần tăng CHARACTER_RANGE để hỗ trợ các bộ ký tự nhiều byte như UTF-8, điều này sẽ trở nên rất tốn bộ nhớ. Do đó, nó chỉ thực sự thiết thực khi số lượng ký tự có thể có trong một phạm vi nhỏ.

Theo quan điểm phát triển, giải pháp này chứa nhiều mã hơn để duy trì và sử dụng ít hơn các hàm thư viện Java.

5. Kiểm tra với MultiSet

Chúng ta có thể đơn giản hóa quá trình đếm và so sánh bằng cách sử dụng MultiSet . MultiSet là một tập hợp hỗ trợ bình đẳng không phụ thuộc vào thứ tự với các phần tử trùng lặp. Ví dụ, các tập đa {a, a, b} và {a, b, a} là bằng nhau.

Để sử dụng Multiset , trước tiên chúng ta cần thêm phần phụ thuộc Guava vào tệp pom.xml dự án của chúng tôi :

 com.google.guava guava 28.1-jre  

Chúng tôi sẽ chuyển đổi mỗi chuỗi đầu vào của chúng tôi vào một MultiSet ký tự. Sau đó, chúng tôi sẽ kiểm tra xem chúng có bằng nhau không:

boolean isAnagramMultiset(String string1, String string2) { if (string1.length() != string2.length()) { return false; } Multiset multiset1 = HashMultiset.create(); Multiset multiset2 = HashMultiset.create(); for (int i = 0; i < string1.length(); i++) { multiset1.add(string1.charAt(i)); multiset2.add(string2.charAt(i)); } return multiset1.equals(multiset2); } 

Thuật toán này giải quyết vấn đề trong thời gian O (n) mà không cần phải khai báo một mảng đếm lớn.

Nó tương tự như giải pháp đếm trước đây. Tuy nhiên, thay vì sử dụng bảng có kích thước cố định để đếm, chúng tôi tận dụng lớp MutlitSet để mô phỏng một bảng có kích thước thay đổi, với số lượng cho mỗi ký tự.

Mã cho giải pháp này sử dụng nhiều khả năng của thư viện cấp cao hơn so với giải pháp đếm của chúng tôi.

6. Đảo chữ dựa trên chữ cái

Các ví dụ cho đến nay không tuân thủ nghiêm ngặt định nghĩa ngôn ngữ của một phép đảo ngữ. Điều này là do họ coi các ký tự dấu câu là một phần của đảo ngữ và chúng có phân biệt chữ hoa chữ thường.

Hãy điều chỉnh các thuật toán để cho phép đảo chữ dựa trên chữ cái. Chúng ta hãy chỉ xem xét việc sắp xếp lại các chữ cái không phân biệt chữ hoa chữ thường, bất kể các ký tự khác như khoảng trắng và dấu chấm câu. Ví dụ: "Một dấu thập phân""Tôi là một dấu chấm tại chỗ." sẽ là đảo ngữ của nhau.

Để giải quyết vấn đề này, trước tiên chúng ta có thể xử lý trước hai chuỗi nhập để lọc ra các ký tự không mong muốn và chuyển đổi các chữ cái thành chữ thường. Sau đó, chúng ta có thể sử dụng một trong các giải pháp trên (giả sử, giải pháp MultiSet ) để kiểm tra các ký tự đảo ngữ trên các chuỗi đã xử lý:

String preprocess(String source) { return source.replaceAll("[^a-zA-Z]", "").toLowerCase(); } boolean isLetterBasedAnagramMultiset(String string1, String string2) { return isAnagramMultiset(preprocess(string1), preprocess(string2)); }

Cách tiếp cận này có thể là một cách chung để giải quyết tất cả các biến thể của vấn đề đảo chữ. Ví dụ: nếu chúng tôi cũng muốn bao gồm các chữ số, chúng tôi chỉ cần điều chỉnh bộ lọc tiền xử lý.

7. Kết luận

Trong bài viết này, chúng tôi đã xem xét ba thuật toán để kiểm tra xem một chuỗi nhất định có phải là một chuỗi đảo chữ của một chuỗi khác, ký tự cho ký tự hay không. Đối với mỗi giải pháp, chúng tôi đã thảo luận về sự cân bằng giữa tốc độ, khả năng đọc và kích thước bộ nhớ cần thiết.

Chúng tôi cũng đã xem xét cách điều chỉnh các thuật toán để kiểm tra đảo chữ cái theo nghĩa ngôn ngữ truyền thống hơn. Chúng tôi đạt được điều này bằng cách xử lý trước các đầu vào thành các chữ cái thường.

Như mọi khi, mã nguồn của bài viết có sẵn trên GitHub.