Valid Anagram

sample_anagramIt seems like anagrams are becoming quite popular in challenges. What is an anagram? The edited definition from Wikipedia follows:

“An anagram is direct word switch or word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. Any word or phrase that exactly reproduces the letters in another order is an anagram”.

Earlier today I made a visit to the LeetCode web site. The computer selected for me a challenge named “Valid Anagram”. The description follows:

Given two strings s and t, write a function to determine if t is an anagram of s. For example,

s = “anagram”, t = “nagaram”, return true.

s = “rat”, t = “car”, return false.

With that in mind I first wrote the following Java program to test the code:

/*

* test code

*/

public static void main(String[] args) {

Scanner sc    = new Scanner(System.in);

System.out.print(“main <<< s: “);

String s      = sc.nextLine();

System.out.print(“main <<< t: “);

String t      = sc.nextLine();

sc.close();

System.out.println(“main <<< s.length: ” + s.length());

System.out.println(“main <<< t.length: ” + t.length());

System.out.println(“main <<< isAnagram: ” + isAnagram(s, t));

}

The task is to write the body of a method with the following signature:

public class Solution {

public boolean isAnagram(String s, String t) {

       }

}

A run of the completed code follows:

main <<< s: anagram

main <<< t: nagaram

main <<< s.length: 7

main <<< t.length: 7

show <<< a : 3

show <<< g : 1

show <<< m : 1

show <<< n : 1

show <<< r : 1

show <<< a : 3

show <<< g : 1

show <<< m : 1

show <<< n : 1

show <<< r : 1

main <<< isAnagram: true

The first word is “anagram”. The second word is “nagaram”. Both words have the same number of characters (7 in this case). The unique characters in the first and second words, in ascending order with their associated frequency, are displayed. It is easy to conclude that this is an anagram. The last line confirms this assumption by printing “true”.

A test for a second set of words follows:

main <<< s: rat

main <<< t: car

main <<< s.length: 3

main <<< t.length: 3

show <<< a : 1

show <<< r : 1

show <<< t : 1

show <<< a : 1

show <<< c : 1

show <<< r : 1

main <<< isAnagram: false

Both words have the same number of characters. As one can see the words do not use the same characters. This is not an anagram. The last line indicates this condition.

The code for the principal method follows:

/*

* determines if the strings are anagrams of each other

*/

public static boolean isAnagram(String s, String t) {

if (s.length() != t.length()) {

return false;

}

TreeMap<Character, Integer> sMap = buildMap(s);

show(sMap);

TreeMap<Character, Integer> tMap = buildMap(t);

show(tMap);

return compareMaps(sMap, tMap);

}

The show() method was used for development and testing only. It should not be part of the solution.

The following code contains the helper methods part of the solution:

/*

* show contents of hashmap

*/

public static void show(Map map) {

Iterator it = map.entrySet().iterator();

while (it.hasNext()) {

Map.Entry pair = (Map.Entry)it.next();

System.out.println(“show <<< ” + pair.getKey() + ” : ” + pair.getValue());

}

System.out.println();

}

/*

* build a tree map of characters and frequencies for specified string

*/

public static TreeMap<Character, Integer> buildMap(String s) {

TreeMap<Character, Integer> map = new TreeMap<Character, Integer>();

for (int i = 0; i < s.length(); i++){

Character c = s.charAt(i);

if (map.containsKey(c)) {

Integer count = map.get(c) + 1;

map.put(c, count);

} else {

map.put(c, 1);

}

}

return map;

}

/*

* compare maps

*/

public static boolean compareMaps(TreeMap<Character, Integer> sMap, TreeMap<Character, Integer> tMap) {

if (sMap.size() != tMap.size()) {

return false;

}

Iterator sIter = sMap.entrySet().iterator();

Iterator tIter = tMap.entrySet().iterator();

while (sIter.hasNext() && tIter.hasNext()) {

Map.Entry sPair = (Map.Entry)sIter.next();

Map.Entry tPair = (Map.Entry)tIter.next();

System.out.println(“compareMaps <<< sPair: ” + sPair.getKey() + ” : ” + sPair.getValue());

System.out.println(“compareMaps <<< tPair: ” + tPair.getKey() + ” : ” + tPair.getValue());

char sc = (char)sPair.getKey();

int si = (int)sPair.getValue();

char tc       = (char)tPair.getKey();

int ti = (int)tPair.getValue();

if ((sc != tc) || (si != ti)) {

return false;

}

}

return true;

}

Note that the code contains debug messages. The code without debug messages was accepted as a solution. It could be modified to improve performance but at this time I have work commitments I need to attend to.

If you have comments or questions, please send me a message via email.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *