2
\$\begingroup\$

Given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other.

Input:

The first line of input contains an integer T denoting the number of test cases. Each test case consist of two strings in 'lowercase' only, in a separate line.

Output:

Print "YES" without quotes if the two strings are anagram else print "NO".

Constraints:

1 ≤ T ≤ 30

1 ≤ |s| ≤ 100

Example:

Input:

2

geeksforgeeks

forgeeksgeeks

allergy

allergic

Output:

YES

NO

My approach:

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.util.HashMap;

class GFG {

    private static String isAnagram (String str1, String str2)
        {
            HashMap <Character, Integer>occurs = new HashMap<>();

            if (str1.length() != str2.length())
                {
                    return "NO";
                }

            for (char ch: str1.toCharArray())
                {
                    if (!(occurs.containsKey(ch)))
                        {
                            occurs.put(ch,1);
                        }
                    else
                        {
                            int count = occurs.get(ch);
                            occurs.put(ch,count + 1);
                        }
                }

            for (char ch: str2.toCharArray())
                {
                    if (!(occurs.containsKey(ch)))
                        {
                            return "NO";
                        }
                    else
                        {
                            int count = occurs.get(ch);
                            count  = count - 1;
                            if (count < 0)
                                {
                                    return "NO";
                                }
                            else
                                {
                                    occurs.put(ch,count);
                                }
                        }
                }

        return "YES";    
        }

    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner (System.in);
        int numTests = sc.nextInt();

        for (int i = 0; i < numTests; i++)
            {
                String str1 = sc.next();
                String str2 = sc.next();
                System.out.println(isAnagram(str1, str2));
            }
    }
}

I have the following questions with regards to the above code:

1) How can I further improve my approach?

2) Is there a better way to solve this question?

3) Are there any grave code violations that I have committed?

4) Can space and time complexity be further improved?

Reference

\$\endgroup\$
2
\$\begingroup\$

Your use of the counting system using a HashMap is a functional approach to solving the problem, and algorithmically it's relatively good (has time complexity of \$O(N)\$). But, for a prolem like this, it's easier to normalize each input value in to a sorted array or string, than in to a counting HashMap.

Consider the following function:

public static final String normalize(value) {
    if (value == null) {
        return null;
    }
    char[] chars = value.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

Now, all values that are anagrams will have the same normalize result (they have the same characters in the same sorted order).

Your code would simply become:

private static String isAnagram (String str1, String str2) {
    return Objects.equals(normalize(str1), normalize(str2));
}

Note that in this case, Objects is java.util.Objects.

Further, by putting the normalization in to a separate function it reduces the amount of logic duplication in your code.

Now, you ask if there are any grave violations... and I have to answer "yes". In Java it is common practice to put { braces on the same line as the code block definition. For example your code:

        for (char ch: str1.toCharArray())
            {
                if (!(occurs.containsKey(ch)))
                    {
                        occurs.put(ch,1);
                    }
                else
                    {
                        int count = occurs.get(ch);
                        occurs.put(ch,count + 1);
                    }
            }

should be:

        for (char ch: str1.toCharArray()) {
            if (!(occurs.containsKey(ch))) {
                occurs.put(ch,1);
            } else {
                int count = occurs.get(ch);
                occurs.put(ch,count + 1);
            }
        }
\$\endgroup\$
  • 4
    \$\begingroup\$ Anirudh simply refuses to use curly braces in a manner consistent with common practice. There are a couple of other things I've seen pointed out to him that he just Doesn't Want To Do. I've given up on being helpful because of it. For fans of streaming, you can also one-line the method as return Arrays.equals(s1.codePoints().sorted().toArray(), s2.codePoints().sorted().toArray()) ? "YES" : "NO"; \$\endgroup\$ – Eric Stein Jul 13 '18 at 18:47
  • \$\begingroup\$ @EricStein Sincere apologies. I didn't know that keeping braces on the new line was a huge violation of coding practices. I will try to improve upon it from next time. \$\endgroup\$ – Anirudh Thatipelli Jul 14 '18 at 3:22
  • \$\begingroup\$ @rofl Isn't sorting the elements take O(n logn) extra time complexity? \$\endgroup\$ – Anirudh Thatipelli Jul 14 '18 at 3:23

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.