The order doesn't matter, as long as both Strings contains exactly the same character and the same number of time they are Anagram. For example, if one letter is repeated on one String and not on other then they will not be Anagram of each other.
Another example of Anagram is "Tokyo" and "Kyoto", two of the most popular cities in Japan. Interestingly both have also served as the capital of Japan, Kyoto was old capital before they moved the capital to Tokyo in the 16th century.
For the sake of simplicity, you can also assume that your solution need not be case-sensitive, which means both army and mary can be matched as an anagram of each other.
Btw, strong knowledge of data structure and algorithm is expected in coding interviews. At the bare minimum, you should be familiar with essential data structures like an array, string, linked list, binary tree, binary search tree, balanced tree, stack, queue, heap, and graphs.
Java Program to find if two String are Anagram or not
Here is a Java program to check if two String is an anagram of each other or not.
import java.util.Arrays;
/**
* Java Program to check if two String is an anagram of each other or not. Two
* String is said to be an anagram of each other, if they contain exactly same
* characters but in a different order. For example "army" and "mary" are anagram
* of each other because they contain exact same characters 'a', 'r', 'm' and
* 'y'.
*
*/
public class Testing {
public static void main(String args[]) {
String[][] data = {{"army", "mary"}, {"stop", "tops"}, {"soap", "abcd"}};
System.out.println("======== Testing areAnagrams() method =======");
for (String[] value : data) {
String s1 = value[0];
String s2 = value[1];
System.out.printf("Are %s and %s are Anagrams? %b%n", s1, s2,
areAnagrams(s1, s2));
}
System.out.println("======== Testing isAnagaram() method =======");
for (String[] value : data) {
String s1 = value[0];
String s2 = value[1];
System.out.printf("Does %s and %s are Anagrams? %b%n", s1, s2,
isAnagram(s1, s2));
}
}
/*
* One of the easiest way to check if two Strings are an anagram of each other
* is to take their character array, sort them and check if they are equal.
* If sorted character arrays are equal then both String are an anagram of
* each other.
*/
public static boolean areAnagrams(String first, String second) {
char[] fa = first.toCharArray();
char[] sa = second.toCharArray();
// sort arrays
Arrays.sort(fa);
Arrays.sort(sa);
// check if arrays are equal
if (Arrays.equals(fa, sa)) {
return true;
}
return false;
}
/*
* Earlier method was using a couple of library methods, which is not permitted during
* interviews. This method checks if two Strings are anagram without using any utility
* method. This solution assumes that both source and target string are ASCII strings.
*/
public static boolean isAnagram(String source, String target) {
if ((source == null || target == null) || source.length() != target.length()) {
return false;
}
int[] table = new int[256];
int numOfUniqueCharInSource = 0;
int numOfCharProcessedInTarget = 0;
char[] characters = source.toCharArray();
// store count of each unique character in source String
for (char ch : characters) {
if (table[ch] == 0) {
++numOfUniqueCharInSource;
}
++table[ch];
}
for (int i = 0; i < target.length(); ++i) {
int c = target.charAt(i);
if (table[c] == 0) {
return false;
}
--table[c];
if (table[c] == 0) {
++numOfCharProcessedInTarget;
if (numOfCharProcessedInTarget == numOfUniqueCharInSource) {
// it’s a match if t has been processed completely
return i == target.length() - 1;
}
}
}
return false;
}
}
Output
======== Testing areAnagrams() method =======
Are army and mary are Anagrams? true
Are stop and tops are Anagrams? true
Are soap and abcd are Anagrams? false
======== Testing isAnagaram() method =======
Does army and mary are Anagrams? true
Does stop and tops are Anagrams? true
Does soap and abcd are Anagrams? false
That's all about how to check if two String is Anagram of each other or not. If you need more String based coding problems for practice then you can also solve problems listed below. It's an interesting problem and there are a couple of invariants as well as the case-sensitive one I discussed in the first paragraph. You may also be asked to calculate the time and space complexity of this problem, can you calculate?
Posts
0 comments:
Post a Comment