An anagram is a word or phrase that is formed by rearranging the letters of another word or phrase. For example, “listen” is an anagram of “silent”.
How to Check if Two Strings are Anagrams in Java
In this program, we will create a method that checks if two given strings are anagrams of each other. We will discuss two common approaches: using sorting and using a frequency count with a hash map.
Solution 1: Using Sorting
This method sorts both strings and checks if they are equal.
import java.util.Arrays;
public class AnagramChecker {
public static void main(String[] args) {
String str1 = "listen";
String str2 = "silent";
boolean result = areAnagrams(str1, str2);
System.out.println("Are \"" + str1 + "\" and \"" + str2 + "\" anagrams? " + result);
}
public static boolean areAnagrams(String str1, String str2) {
// Remove spaces and convert to lowercase
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
// Check if lengths are different
if (str1.length() != str2.length()) {
return false; // Not anagrams if lengths differ
}
// Sort both strings
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
// Compare sorted arrays
return Arrays.equals(charArray1, charArray2);
}
}
Line-by-Line Execution Explanation for Solution 1
- Method Declaration:
public static boolean areAnagrams(String str1, String str2) {
- This method accepts two strings as parameters and returns a boolean indicating whether they are anagrams.
- Remove Spaces and Convert to Lowercase:
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
- This line removes any spaces and converts both strings to lowercase to ensure the comparison is case insensitive and space insensitive.
- Length Check:
if (str1.length() != str2.length()) {
return false; // Not anagrams if lengths differ
}
- If the lengths of the strings are not the same, they cannot be anagrams, so it returns
false.
- Sort Both Strings:
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
- Converts the strings to character arrays and sorts them.
- Compare Sorted Arrays:
return Arrays.equals(charArray1, charArray2);
- Compares the sorted arrays. If they are equal, the strings are anagrams; otherwise, they are not.
Time Complexity
- O(n log n), where n is the length of the strings (due to the sorting step).
Space Complexity
- O(n) for storing the character arrays.
Solution 2: Using Frequency Count with HashMap
This method uses a hash map to count the frequency of each character.
import java.util.HashMap;
public class AnagramChecker {
public static void main(String[] args) {
String str1 = "listen";
String str2 = "silent";
boolean result = areAnagrams(str1, str2);
System.out.println("Are \"" + str1 + "\" and \"" + str2 + "\" anagrams? " + result);
}
public static boolean areAnagrams(String str1, String str2) {
// Remove spaces and convert to lowercase
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
// Check if lengths are different
if (str1.length() != str2.length()) {
return false; // Not anagrams if lengths differ
}
// Frequency map for characters
HashMap<Character, Integer> frequencyMap = new HashMap<>();
// Count frequency of each character in the first string
for (char c : str1.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
// Subtract frequency using the second string
for (char c : str2.toCharArray()) {
if (!frequencyMap.containsKey(c)) {
return false; // Character not found
}
frequencyMap.put(c, frequencyMap.get(c) - 1);
if (frequencyMap.get(c) < 0) {
return false; // More occurrences than in str1
}
}
return true; // All counts should be balanced
}
}
Line-by-Line Execution Explanation for Solution 2
- Method Declaration:
public static boolean areAnagrams(String str1, String str2) {
- Similar to Solution 1, this method accepts two strings as parameters.
- Remove Spaces and Convert to Lowercase:
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
- This line is identical to Solution 1, ensuring uniformity in comparison.
- Length Check:
if (str1.length() != str2.length()) {
return false; // Not anagrams if lengths differ
}
- If the lengths differ, it returns
false.
- Frequency Map Initialization:
HashMap<Character, Integer> frequencyMap = new HashMap<>();
- A hash map is initialized to store the frequency of each character.
- Count Frequency of Characters in
str1:
for (char c : str1.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
- This loop counts the occurrences of each character in the first string.
- Subtract Frequency Using
str2:
for (char c : str2.toCharArray()) {
if (!frequencyMap.containsKey(c)) {
return false; // Character not found
}
frequencyMap.put(c, frequencyMap.get(c) - 1);
if (frequencyMap.get(c) < 0) {
return false; // More occurrences than in str1
}
}
- For each character in
str2, it checks if it exists in the frequency map. - If it does, it decreases the count. If the count goes negative, it returns
false.
- Return True:
return true; // All counts should be balanced
- If all character counts are balanced, it returns
true.
Time Complexity
- O(n), where n is the length of the strings.
Space Complexity
- O(k), where k is the number of unique characters in the strings.
Conclusion
In this guide, we explored two methods to check if two strings are anagrams in Java:
- Using Sorting – Simple and effective but has a higher time complexity due to sorting.
- Using Frequency Count – Efficient for large inputs and has a linear time complexity.
Looking for Career Opportunities?
If you’re preparing for coding interviews or looking for career guidance, feel free to submit your resume to Divi Tech Careers at Divi Tech Careers. You can also reach out for personalized career advice via info@divisolutions.in.
0 Comments