Last active
July 18, 2017 12:59
-
-
Save u6f6o/b66bd79fd2f7a1c87bd9f6b440bf347f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Anagram { | |
| private static final long [] FIRST_26_PRIMES = new long [] { | |
| 2, | |
| 3, | |
| 5, | |
| 7, | |
| 11, | |
| 13, | |
| 17, | |
| 19, | |
| 23, | |
| 29, | |
| 31, | |
| 37, | |
| 41, | |
| 43, | |
| 47, | |
| 53, | |
| 59, | |
| 61, | |
| 67, | |
| 71, | |
| 73, | |
| 79, | |
| 83, | |
| 89, | |
| 97, | |
| 101 | |
| }; | |
| private static final int A_Z_SIZE = Character.getNumericValue('Z') - Character.getNumericValue('A') + 1; | |
| private static final int CHARACTER_A_OFFSET = Character.getNumericValue('a'); | |
| /** | |
| * This method assume all characters of string s1 and s2 being one of [a-zA-Z]. There is no | |
| * distinction made between upper-case and lower-case letters, so 'Aba' would be an valid | |
| * anagram of 'baa'. | |
| * <p/> | |
| * Initially the length of both strings is compared, if they are not equal, they are not | |
| * anagrams. Also if the strings are empty, they are not considered Anagrams. | |
| * <p/> | |
| * If the given strings are of length < 9, a prime multiplication method is used, otherwise | |
| * a fixed size array of length 26 is used as a representation of a histogram. | |
| * | |
| * @param s1 not-null string of arbitrary length | |
| * @param s2 not-null string of arbitrary length | |
| * @return is anagram true/false | |
| */ | |
| public static boolean isAnagram(String s1, String s2) { | |
| if (s1.length() != s2.length() || s1.length() < 1) { | |
| return false; | |
| } | |
| if (s1.length() < 10) { | |
| return isAnagramUsingPrimes(s1, s2); | |
| } | |
| return isAnagramUsingArray(s1, s2); | |
| } | |
| private static boolean isAnagramUsingPrimes(String s1, String s2) { | |
| long product = 1L; | |
| for (int i = 0; i < s1.length(); i++) { | |
| int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET; | |
| long currPrime = FIRST_26_PRIMES[currChar]; | |
| product *= currPrime; | |
| } | |
| for (int i = 0; i < s2.length(); i++) { | |
| int currChar = Character.getNumericValue(s2.charAt(i)) - CHARACTER_A_OFFSET; | |
| long currPrime = FIRST_26_PRIMES[currChar]; | |
| if (product % currPrime != 0) { | |
| return false; | |
| } | |
| product /= currPrime; | |
| } | |
| assert product == 1L; | |
| return true; | |
| } | |
| private static boolean isAnagramUsingArray(String s1, String s2) { | |
| int [] countsArray = new int[A_Z_SIZE]; | |
| for (int i = 0; i < s1.length(); i++) { | |
| int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET; | |
| int count = countsArray[currChar]; | |
| countsArray[currChar] = count + 1; | |
| } | |
| for (int i = 0; i < s2.length(); i++) { | |
| int currChar = Character.getNumericValue(s2.charAt(i)) - CHARACTER_A_OFFSET; | |
| int count = countsArray[currChar]; | |
| if (count == 0) { | |
| return false; | |
| } | |
| countsArray[currChar] = count - 1; | |
| } | |
| return true; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment