In this post we will be solving the LeetCode 242 Valid Anagram problem using the Java programming language.
Given two strings s and t, return true if t is an anagram of s, and false otherwise. Constraints: o 1 <= s.length, t.length <= 5 * 10^4 o s and t consist of lowercase English letters. Related Topics: o Hash Table o String o Sorting
We are given two strings. We need to determine if one string is the anagram of the other.
It seems that if one string is the anagram of the other we should be able to check our solution using `s` on `t` or vice versa. We should also note that the length of both strings should be the same since anagrams must contain the same number of letters.
We will be solving this problem using the Java programming language and the VSCode IDE on the Windows platform.
public boolean isAnagram(String s, String t) {
}
The signature for the function of interest requires as arguments two strings and it should return true or false following the requirement description.
I will be using my own computer to solve this problem. My suggestion is for you to use the online IDE provided by LeetCode. That way you will not be required to generate a simple test scaffold. In this post I will be writing some test code which IS NOT PART OF THE SOLUTION!
anagram, nagaram main <<< s ==>anagram<== main <<< t ==>nagaram<== main <<< isAnagram0: true main <<< isAnagram1: true main <<< isAnagram2: true main <<< isAnagram3: true main <<< isAnagram: true anagram, amagram main <<< s ==>anagram<== main <<< t ==>amagram<== main <<< isAnagram0: false main <<< isAnagram1: false main <<< isAnagram2: false main <<< isAnagram3: false main <<< isAnagram: false anagram, agraman main <<< s ==>anagram<== main <<< t ==>agraman<== main <<< isAnagram0: true main <<< isAnagram1: true main <<< isAnagram2: true main <<< isAnagram3: true main <<< isAnagram: true rat, car main <<< s ==>rat<== main <<< t ==>car<== main <<< isAnagram0: false main <<< isAnagram1: false main <<< isAnagram2: false main <<< isAnagram3: false main <<< isAnagram: false
Each test case is separated by using two blank lines.
The first line contains the two strings we will be using as arguments for the function of interest.
Our test code seems to read the input line and populate the two strings ‘s’ and ‘t`. The contents of the strings are then displayed to make sure all is well so far.
Our test code seems to call five different implementations. After each implementation is called the associated result is displayed.
/**
* Test scaffod.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read input strings ****
String[] strArr = br.readLine().trim().split(", ");
// **** close buffered reader ****
br.close();
// **** for ease of use ****
String s = strArr[0];
String t = strArr[1];
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
System.out.println("main <<< t ==>" + t + "<==");
// **** call function of interest and display result ****
System.out.println("main <<< isAnagram0: " + isAnagram0(s, t));
// **** call function of interest and display result ****
System.out.println("main <<< isAnagram1: " + isAnagram1(s, t));
// **** call function of interest and display result ****
System.out.println("main <<< isAnagram2: " + isAnagram2(s, t));
// **** call function of interest and display result ****
System.out.println("main <<< isAnagram3: " + isAnagram2(s, t));
// **** call function of interest and display result ****
System.out.println("main <<< isAnagram: " + isAnagram(s, t));
}
This is our test scaffold. Please note that IT IS NOT PART OF THE SOLUTION!
The code reads the input line and populates the two arguments for the function of interest. A set of implementations are called and the results displayed.
/**
* Given two strings s and t,
* return true if t is an anagram of s, and false otherwise.
* Sort char[] arrays and compare.
*
* Runtime: O(n ^ 2) - Space: O(1)
*
* 36 / 36 test cases passed, but took too long.
* Status: Time Limit Exceeded
*/
static public boolean isAnagram0(String s, String t) {
// **** sanity checks ****
if (s.length() != t.length()) return false;
// **** initialization ****
char[] arr1 = s.toCharArray();
char[] arr2 = t.toCharArray();
// **** sort char[] arrays - O(n ^ 2) ****
sort(arr1);
sort(arr2);
// **** traverse arrays comparing characters - O(n) ****
for (int i = 0; i < arr1.length; i++)
if (arr1[i] != arr2[i]) return false;
// **** strings are anagrams ****
return true;
}
In this approach we generate two char[] arrays with the characters for each string.
The arrays are then sorted using an auxiliary function.
We then traverse both arrays checking that the characters match. While we are traversing the arrays, we check if we encounter a pair in which the characters do not match. If so we return `false`.
If we traverse all the characters in the arrays, we return `true` to indicate that both strings are anagrams.
/**
* Sort character array in place.
* Auxiliary function.
*
* Runtime: O(n ^ 2) - Space: O(1)
*/
static private void sort(char[] arr) {
// **** sanity check ****
if (arr.length == 1) return;
// **** initialization ****
char tmp;
int len = arr.length;
int i = 0;
int j = 0;
// **** O(n ^ 2) ****
while (i < len) {
// **** set index ****
j = i + 1;
// **** sort characters remeining characters - O(n) ****
while (j < len) {
// **** swap characters (if needed) ****
if (arr[i] > arr[j]) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// **** increment index ****
j++;
}
// **** increment index ****
i++;
}
}
The auxiliary function sorts the contents of the specified array. It seems to work fine, but execution is O(n ^ 2) which in general is quite slow.
Take a look at the comments section of this implementation. It seems that all test cases passed, but the execution time was not good enough to accept it. Let’s see if we can improve on the execution time.
/**
* Given two strings s and t,
* return true if t is an anagram of s, and false otherwise.
* Using hashmap.
*
* Runtime: O(n) - Space: O(n)
*
* 36 / 36 test cases passed.
* Status: Accepted
* Runtime: 9 ms
* Memory Usage: 39.5 MB
*/
static public boolean isAnagram1(String s, String t) {
// **** sanity checks ****
if (s.length() != t.length()) return false;
// **** initialization ****
HashMap<Character, Integer> hm = new HashMap<>(s.length());
// **** populate hashmap - O(n) ****
for (char ch : s.toCharArray()) {
Integer cnt = hm.putIfAbsent(ch, 1);
if (cnt != null) hm.put(ch, ++cnt);
}
// *** traverse t removing values from hm - O(n) ****
for (char ch : t.toCharArray()) {
// **** get character count ****
Integer cnt = hm.get(ch);
// **** character not found ****
if (cnt == null) return false;
// **** update hashmap ****
if (--cnt > 0) hm.put(ch, cnt);
else hm.remove(ch);
}
// **** check if hashmap is empty ****
return hm.size() == 0 ? true : false;
}
In this implementation we will use a hashmap. We will populate the hashmap with the counts of the characters in string `s`.
We will then traverse the second string `t` while decrementing the counts on the hashmap. When the count for a character reaches zero, the entry is removed from the hashmap.
When all is said and done, if the strings are anagrams, the hashmap should be empty.
Take a look at the comments in this implementation. The code was accepted. That said; perhaps we could do better.
/**
* Given two strings s and t,
* return true if t is an anagram of s, and false otherwise.
* Using hashmap.
*
* Sort char[] arrays.
*
* 36 / 36 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 39.3 MB
*/
static public boolean isAnagram2(String s, String t) {
// **** sanity checks ****
if (s.length() != t.length()) return false;
// **** initialization ****
char[] arr1 = s.toCharArray();
char[] arr2 = t.toCharArray();
// **** sort char[] arrays ****
Arrays.sort(arr1);
Arrays.sort(arr2);
// **** traverse char[] arrays comparing characters - O(n) ****
for (int i = 0; i < arr1.length; i++)
if (arr1[i] != arr2[i]) return false;
// **** strings are anagrams ****
return true;
}
In this implementation we will use two char[] arrays each associated with one of the string arguments.
Instead of sorting the arrays using an auxiliary function, we will sort them using the Arrays class.
Once both arrays are sorted, we traverse the arrays checking if the counts for the characters match. If not; the strings are not anagrams and the function returns `false`.
If we complete the loop, then the strings are anagrams.
Please look at the comments section of this implementation. It seems that we improved on our last implementation.
/**
* Given two strings s and t,
* return true if t is an anagram of s, and false otherwise.
* Using hashmap.
*
* Counting characters in both strings then comparing results.
* Similar to using two hashmaps but considerably faster.
*
* Runtime: O(n) - Space: O(n)
* 36 / 36 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 39.2 MB
*/
static public boolean isAnagram3(String s, String t) {
// **** sanity checks ****
if (s.length() != t.length()) return false;
// **** initialization ****
int[] freq1 = new int[256];
int[] freq2 = new int[256];
// **** populate int[] freq1 - O(n) ****
for (char ch : s.toCharArray())
freq1[ch]++;
// **** populate int[] freq2 - O(n) ****
for (char ch : t.toCharArray())
freq2[ch]++;
// **** compare frequencies of lowercase characters - O(n) ****
for (int i = 'a'; i <= 'z' ; i++)
if (freq1[i] != freq2[i]) return false;
// **** strings are anagrams ****
return true;
}
In this implementation of the function of interest we use two int[] arrays which are populated with the counts of the characters of each string. This is similar to using a hashmap since each character has a count for each string.
After populating both arrays we compare the counts. If a count is not a match, we return `false` to indicate the strings are not anagrams.
If we reach the end of the last loop, we return `true` to indicate that the strings are anagrams.
If you check the comments section of this implementation we were able to shave 1 millisecond from the previous code.
/**
* Given two strings s and t,
* return true if t is an anagram of s, and false otherwise.
* Using hashmap.
*
* Counting characters in both strings then comparing results.
* Similar to using a single hashmap but considerably faster.
*
* 36 / 36 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 38.7 MB
*
* Runtime: 1 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.7 MB, less than 99.76% of Java online submissions.
*/
static public boolean isAnagram(String s, String t) {
// **** sanity checks ****
if (s.length() != t.length()) return false;
// **** initialization ****
int[] freq = new int[256];
// **** increment characters frequencies - O(n) ****
for (char ch : s.toCharArray())
freq[ch]++;
// **** decrement character frequencies - O(n) ****
for (char ch : t.toCharArray())
freq[ch]--;
// **** check character frequencies - O(n) ****
for (int i = 'a'; i <= 'z' ; i++)
if (freq[i] != 0) return false;
// **** strings are anagrams ****
return true;
}
In this implementation we use a single int[] array to keep track of the frequencies of the characters from the first string.
We then traverse the second string decreasing the frequency counts. If a frequency goes negative, the strings are not anagrams and we return `false`.
If we reach the last statement in the function we return `true` since the strings are anagrams of each other.
Please take a look at the comments section in this implementation. It appears that it is 1 millisecond faster than 100% of the submissions!
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named ValidAnagram.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John