4
\$\begingroup\$

My code passes all the given test cases. I would like to know a better way to to write the code. Such as a more efficient algorithm for checking if two strings are anagrams.

import java.io.* ;
import java.util.* ;

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    
    String  str1 = input.nextLine().toLowerCase();
    String str2 = input.nextLine().toLowerCase();
    
    char[] temp = str1.toCharArray(); Arrays.sort(temp);
    str1 = new String(temp);
    
    temp = str2.toCharArray(); Arrays.sort(temp);
    str2 = new String(temp);
            
    if(str1.equals(str2) == true) System.out.println("Anagrams");
    else System.out.println("Not Anagrams");
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ To review the efficiency and correctness of your code, I'd like to clarify on limitations and see some test-cases (whitespace, words only, sentence with punctuation, ASCII or broader charsets). The interpretation of anagrams may vary I suppose. \$\endgroup\$
    – hc_dev
    Jul 2 at 19:17
  • 1
    \$\begingroup\$ Welcome to Code Review Akshay Reddy. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the question and answer style of Code Review. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Peilonrayz
    Jul 2 at 19:23
  • \$\begingroup\$ @Peilonrayz Sure, I'll avoid changes to my question! Instead I'll answer to my own question and make changes there! \$\endgroup\$ Jul 2 at 19:30
7
\$\begingroup\$

Provide Context

Explain what it does in a meaningful method name and JavaDoc comment (in your question as well)

Example:

/**
 * Test if both words are anagrams to each other.
 * <p>Works for lowercase ASCII only.
 * 
 * word           non-blank lowercase word (may have spaces inside)
 * otherWord      ...
 * return         true if word is anagram of otherWord, false else 
 */
public static boolean areAnagrams(String word, String otherWord) {
   // check if anagrams
   return true;
   // if not
   return false;
}

What the method signature reveals to the code reader already:

  • public so he can use it
  • static behaviour does not depend on class state (each execution is determined by parameters only)
  • boolean return signals a kind of test-function, that can be used in if-statments, etc.
  • areAnagrams tells what it does (Java-naming convention for boolean tests is prefixing with is, are, has, etc.)

The JavaDoc explains limitations and should also list expected parameters and what is returned when, or what Exception is thrown when errors occur.

Naming

  • method: should tell the caller immediately what it does (main is not a catch-all container)
  • variable: str1, str2 tell nothing about their purpose (like inputLine or potentialAnagram. temp is even worse (what's in it, where comes from). input is misleading, because it's a scanner to look and extract input from later.

Separation of Concerns

  • UI and business-logic should always be separated: text input/output is one concern (class or method) to find similarly in many applications; logic (find anagrams, test and calculate result) are another concern to focus on with domain knowledge;

Why separate (benefits)?

Both can be developed/maintained/adapted/exchanged separately and by different persons simultaneously. They are glued together and aimed to fit like a puzzle by "contract" or design. Here for example: (a) the input provided to logic should always be 2 strings (arbitrary length, non-blank, etc.); whereas the output to the user should be a descriptive message in 2 variants for is-anagram or is-not..; (b) the logic accepts two strings and returns a boolean; (c) the UI-layer should validate input and reject invalid like two empty string; (d) the UI-layer should also convert response from logic like boolean to an output message (it may use the input like "Given line 1 'Ana' and 2 'Gram' are NO anagrams")


These 3 categories are just to ease code reading and understanding. Still they may lead to better problem thinking, improve design and optimize implementation.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ It's one function that takes 2 strings. Short numbered var names are appropriate here. The function name already tells you what the strings vars are. potentialAnagram1 / potentialAnagram2 would just be more typing for no increase in clarity. Like if you had a function that did return x*y, I wouldn't say it would be better if the vars were called multiplicandX and multiplicandY. Tiny functions with few variables are one of the few cases where it's ok to give up on meaningful names. \$\endgroup\$ Jul 2 at 15:38
  • \$\begingroup\$ Your choice of word and otherWord is ok and does remind users that it should be a single word, though, so that's good. I'd prefer word1 and word2. \$\endgroup\$ Jul 2 at 15:40
  • \$\begingroup\$ I think str1 and str2 are fine here. It's just comparing two arbitrary strings, there's nothing more to them. Using word in the name suggests that they can't contain punctuation, or they should be actual words in some language, etc. \$\endgroup\$
    – Barmar
    Jul 2 at 18:44
  • 1
    \$\begingroup\$ can be smelly yes, like in that example you linked where it's employee vs. employee2, and there is some semantic difference between them so more meaningful names are possible. Notice that I suggested word1 and word2, not word and word2. I think foo / anotherFoo is actually worse because it implies one has to be the "reference" or original, not just two interchangeable operands, and they're different lengths so the same code repeated for both variables will potentially look more different than it needs to. \$\endgroup\$ Jul 2 at 19:16
  • 1
    \$\begingroup\$ (1 vs. 2 could unfortunately imply order, but I think that's the lesser of two evils here. This function is commutative, but hopefully that's understood as inherent from how anagrams work. In old C code, it was common to use p and q for char* strings, e.g. for implementing strcmp or something which has the same kind of naming problem as here. p and q are the string-pointer equivalent of i, j, k loop counter variables. I wouldn't actually suggest using those names in Java code, but it's interesting that that older coding style solved this problem cleanly.) \$\endgroup\$ Jul 2 at 19:20
6
\$\begingroup\$

Sure.

  • Create a table of all possible characters (as we talk unicode today, this should not really be a table but rather a hash map or the like.)
  • Pass over string 1, recording the character count in the table (i.e. increment the count for each character you encounter.)
  • Pass over string 2, decreasing the character count in the table for each character you encounter
  • If all counts are zero, you have an anagram.

If we assume input length is \$n\$ and the table size is \$m\$ you'll have two passes of \$m\$ for table initialization and evaluation plus two passes of \$n\$ for the string, which comes down to \$O(n+m)\$.

\$\endgroup\$
0
6
\$\begingroup\$

One line - one statement

This will make the code more readable.

temp = str2.toCharArray();
Arrays.sort(temp);
str2 = new String(temp);
        
if(str1.equals(str2) == true) 
    System.out.println("Anagrams");
else 
    System.out.println("Not Anagrams");

Separate logic and input/output

This look much cleaner:

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    String  str1 = input.nextLine().toLowerCase();
    String str2 = input.nextLine().toLowerCase();

    if(isAnagram(str1, str2))
        System.out.println("Anagrams");
    else 
        System.out.println("Not Anagrams");
}
bool isAnagram(String s1, String s2) {...}

All the logic is in isAnagram function; it doesn't mix with input/output and can potentionally be reused in other projects.

Be careful with Unicode

If you are using non-ASCII characters, the effects of toLowerCase/toUpperCase and breaking into characters can be unexpected, like "ß".toUpperCase() producing "SS" or "á" being two characters. I'll assume you're using ASCII character set.

Use Arrays.equals

Arrays.equals method can compare arrays, so you can avoid gathering arrays back in strings.

Algorithm

To compare to strings for being anagrams, you need to find every symbol of one string in another (naive algorithm will give \$O(n^2)\$), and sorting makes it faster (\$O(n log(n))\$). Could it be even faster? Maybe - if you choose the proper sorting algorithm. If you're using ASCII characters only and words are long enough (tens of characters), counting sort will allow you to exchange some memory for speed. You don't even need to recreate a sorted sequence - just:

  1. compare lengths
  2. add the number of characters in the first string
  3. subtract the number of characters in the second string, if you ever get a negative value - the strings are not anagrams.
\$\endgroup\$
9
  • 7
    \$\begingroup\$ isAnagrams should either be isAnagram (is x an anagram of y) or areAnagrams (are these words anagrams of each other). isAnagrams isn't valid English grammar. >.< \$\endgroup\$ Jul 2 at 15:42
  • \$\begingroup\$ Thanks @PeterCordes, fixed! \$\endgroup\$ Jul 2 at 15:47
  • 1
    \$\begingroup\$ You can squeeze out O(n) if you build a histogram of each word (mapping characters to their counts) in linear time, then doing a linear time hashmap equality comparison. But in practice, the memory/allocation overhead of all the objects involved in prosecuting a HashMap ends up drowning out any theoretical asymptotic benefit because real words are very short. \$\endgroup\$
    – Alexander
    Jul 2 at 18:09
  • \$\begingroup\$ @Alexander: You don't need a hash map if the character-set is narrow enough (e.g. 7-bit ASCII), which makes the method a lot more likely to be worth it for as few as ~20 characters. This answer already suggests an improvement on your method, histogramming char counts into an array for one string, then decrementing for the other string, giving you an early-out as well as O(N) worst-case. And just one memory allocation, for an array of 256 int elements (or even 16 or 8-bit to make zero-init and all-zero-check cheaper, if the input string is <256 chars so can't overflow a bucket). \$\endgroup\$ Jul 2 at 19:27
  • 1
    \$\begingroup\$ @Alexander: Ok, then I guess you should post an answer explaining that toCharArray / sort is broken for the general case of Unicode. Note that it's relatively speedy to check a UTF-8 (or a UTF-16) string for not having any multi-byte characters, or optimistically start with that assumption for long strings and convert your 128-entry array to a HashMap only if you encounter a larger character. (At least it's speedy if you can get the runtime to use SIMD to check 16 bytes at a time, i.e. just OR string data together and check at the end if any bits outside the low 7 are set.) \$\endgroup\$ Jul 2 at 19:36
4
\$\begingroup\$

Consider whitespace and symbols. Do you want "parliament" and "partial men" to match? How about "Internet Anagram Server" and "I, Rearrangement Servant"?

\$\endgroup\$
0
3
\$\begingroup\$

You fell into an often-overlooked trap, which makes your program useless to most of the world. It assumes that one char is one "character" (as users would understand it). Here's where that goes wrong:

🇧🇬
🇬🇧
Anagrams

The first input is the flag of Bulgaria, and the second is the flag of Great Britain. You see, there isn't actually a dedicated Unicode code point for every flag. Instead, there are 26 regional indicator symbols, one for each of the 26 English letters. These are combined into ISO 3166-2 2-letter country codes. In this case, "[B][G]" and "[G][B]". It's then the system's responsibility to identify these country codes, and present a single glyph which shows the latest flag for that country code.

Your program considers these to be anagrams. It would fail in similar spectacular ways for skin-tone-modified emojis, family emojis, many non-latin alphabets (including popular ones like Chinese).

The solution is to operate on the level of "Unicode Extended Grapheme Clusters" rather than chars (which model Unicode scalars). This is the closest thing to a human's understanding of "characters", accounting for things like emoji families, flags, characters with accent modifiers applied to them, and so on. It's not a perfect match, but it's pretty close.

This code snippet from this answer looks like a pretty promising way to decompose a string into its constituent EGCs:

String[] extendedGraphemeClusters = inputString.codePoints()
    .mapToObj(cp -> new String(Character.toChars(cp)))
    .toArray(size -> new String[size]);

You could then use this extendedGraphemeClusters array of strings (where each string is really just an EGC) as the input to the various algorithms discussed in the other answers. E.g. you can use that array with the sorting approach you used originally. Rather than sorting the characters with the input string, you would sort the strings (modeling EGCs) in the array (which models the EGCs of the input string).

You could also use the HashMap based approach with it, just the same.

\$\endgroup\$
3
\$\begingroup\$

Add a check of length comparison before sorting. When length of both strings are not same then it should just return false. This will save you on sorting of string performance especially for large input strings.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Great aspect: that pre-condition allows for fail-fast return. \$\endgroup\$
    – hc_dev
    Jul 5 at 17:14
1
\$\begingroup\$

Sorting takes O(N*log(N)), so of course there is an efficient way to check for Anagrams. Here is an efficient O(N) Time & Space approach to check Anagrams.
Steps involved in checking for ANAGRAMS:

  1. If the length of both strings is unequal, then they can never be Anagrams.
  2. Convert the strings to Lowercase characters to save memory (as then we only need to deal with 26 characters).
  3. Count the frequency of all the alphabets between 'a' to 'z' for both the strings for comparison.
  4. Compare the frequency of all the alphabets from 'a' to 'z' of both strings as for being Anagrams to each other, the frequency of each character for both the strings should be equal.
  5. If the frequency of any character is found to be unequal, break the loop as it can't be an Anagram. Else they are anagrams.
    static boolean isAnagram(String s1, String s2)
    {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 != n2)
            return false;
        
        int freq[] = new int[26];
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        
        for (int i=0; i<n1; i++)    ++freq[ c1[i]-'a' ];
        for (int i=0; i<n2; i++)    --freq[ c2[i]-'a' ];
        
        for (int i=0; i<26; i++)
            if ( freq[i] != 0 )
                return false;
        return true;
    }

If the string contains characters other than alphabets we need to use a freq array of size 128 or 256 (for extended ASCII characters).

\$\endgroup\$
0
\$\begingroup\$

My Code, After few changes made according to fellow user's valuable comments...

Previously my code was able to check only words, now it can able to check (Whitespace, Words only, Sentence with Punctuation). I added the trim() method to both the anagrams strings in the code.

static boolean isAnagram(String x, String y) {
    char[] temp = x.toLowerCase().toCharArray();
    Arrays.sort(temp);
    x = new String(temp);
    
    temp = y.toLowerCase().toCharArray();
    Arrays.sort(temp);
    y = new String(temp);
    
    return x.trim().equals(y.trim());
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    
    if(isAnagram(in.nextLine(), in.nextLine()))
        System.out.println("Anagrams");
    else 
        System.out.println("Not Anagrams");
}

I can't use Arrays.equals() method as I can't trim character array, also I can't use equalsIgnoreCase() just to avoid toLowerCase() as it fails in case like Parliament and partial men.

If the above words are given to program input, the line goes like this if("Paaeilmnrt".trim().equalsIgnoreCase(" aaeilmnprt".trim()) which results in false.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ OK. Which review advice did you incorporate and would suggest to future visitors.? At least encapsulation into a function would make it easy to test and reuse/interchange implementation in the future. A test would reveal missing input-validation since passing 2 empty or same-length blank strings results in equality and outputs "Anagrams". Could merge toLowerCase + equals to equalsIgnoreCase. \$\endgroup\$
    – hc_dev
    Jul 2 at 20:36
  • \$\begingroup\$ This doesn't appear to have any of the efficiency or separation ideas suggested in other answers. e.g. still converting back to Strings instead of Arrays.equals from Pavlo's answer. The only change appears to be avoiding putting 2 statements on one line, and handling whitespace with trim. \$\endgroup\$ Jul 3 at 0:46
  • 1
    \$\begingroup\$ @hc_dev: Why wouldn't the empty string be an anagram of itself? Both strings have the same set of visible characters, the empty set. \$\endgroup\$ Jul 3 at 0:49
  • 1
    \$\begingroup\$ @PeterCordes, Does an empty string has visible characters (consider length() == 0) and is "" really a valid anagram? AFAIK: Anagram is rearranged characters. If no characters, then no rearrangement. For same reason I would see a single character String also invalid subject for an anagram. \$\endgroup\$
    – hc_dev
    Jul 3 at 12:45
  • 1
    \$\begingroup\$ @hc_dev: Semantic / English definition arguments like that are separate from checking whether the strings use the same set of letters, which is what this function really does. You could rename it sameVisibleCharacters if you want to limit its responsibility to just what it currently does, leaving it up to the caller to decide whether degenerate cases "don't count". Palindrome checkers would normally return true for single-letter inputs, and probably the empty string, even though those are trivial. I guess if you want to reject <= 1 char after whitespace filtering, it makes sense here. \$\endgroup\$ Jul 3 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.