Question

Two strings are anagrams if they are permutations of each other. For example, "ear" and "era", "rate" and "tear", "evil" and "vile", and "listen" and "silent", are anagrams. In this problem you will write two methods that decide whether two input strings are anagrams. Assume here that all characters are lower-case letters. a) [10 Points] Write a method public static boolean anagramSort(String str1, String str2) that decides whether two input strings are anagrams by sorting them and checking whether they are equal in the sorted order. Your method must have time complexity O(nlogn), where n is the length of the input strings. b) [15 Points] Write a method public static boolean anagramCount(String str1, String str2) that decides whether two input strings are anagrams by counting and comparing the number of times each letter occurs in the strings, using an array of length 26 for each. Your method must have time complexity O(n), where n is the length of the input strings.

Answer 1

a) The method public static boolean anagramSort(String str1, String str2) checks if two input strings are anagrams by sorting them and comparing whether they are equal in the sorted order.

b) The method public static boolean anagramCount(String str1, String str2) determines if two input strings are anagrams by counting and comparing the frequency of each letter in the strings using arrays of length 26.

Step-by-step explanation:

For part (a), the method anagramSort sorts the input strings, making the comparison process straightforward. Sorting has a time complexity of O(n log n), where n is the length of the input strings. The equality check between the sorted strings also has a time complexity of O(n). Therefore, the overall time complexity is O(n log n).

In part (b), the method anagramCount utilizes an array of length 26 to count the occurrences of each letter in the input strings. The counting process has a time complexity of O(n) as each character is visited once. After counting, it compares the counts, again with a time complexity of O(n). Therefore, the overall time complexity is O(n), which is more efficient than the sorting approach.

In conclusion, the anagramCount method offers a more efficient solution for determining if two strings are anagrams compared to the anagramSort method. The counting method achieves linear time complexity, making it preferable for larger inputs, while the sorting method has a higher time complexity of O(n log n).