Lets Code Everyday - Day 25

Question - 25:

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

First approach:

class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length()!=t.length()) return false;

         char[] sArr= s.toCharArray();
         char[] tArr= t.toCharArray();

         Arrays.sort(sArr);
         Arrays.sort(tArr);

         String sNew= new String(sArr);
         String tNew= new String(tArr);

     return sNew.equals(tNew);
    }            
}

Step-by-step implementation:

1. The method isAnagram takes two string inputs s and t and returns a boolean value.

2. The first line of the method checks if the length of s is not equal to the length of t. If the lengths are not equal, the method returns false because anagrams must have the same length.

3. The method creates two character arrays sArr and tArr from the input strings s and t, respectively. A character array is an array of characters that can be manipulated using various built-in methods.

4. The Arrays.sort() method is used to sort the character arrays sArr and tArr in alphabetical order. Sorting the arrays is necessary because anagrams have the same letters but may be in different orders.

5. The sorted character arrays sArr and tArr are then converted back into strings sNew and tNew using the String constructor.

6. Finally, the method returns true if the two strings sNew and tNew are equal, which means they contain the same characters in the same order. Otherwise, the method returns false.

In summary, this method determines if two strings are anagrams of each other by checking if they have the same length, sorting their characters alphabetically, and comparing the sorted strings to see if they are equal.

The time complexity of the given code is O(n log n), where n is the length of the input strings, due to the sorting algorithm used, and the space complexity is O(n) because the method creates two character arrays of size n and two string objects of size n.

Second approach:

class Solution {
   public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) return false;

        StringBuilder t1 = new StringBuilder(t);
        for (char ch : s.toCharArray()) {
            if (t1.toString().contains(ch + "")) {
                t1.deleteCharAt(t1.indexOf(ch + ""));
            }
        }

    return t1.toString().isEmpty();
    }        
}

Step-by-step implementation:

1. The method isAnagram takes two string inputs s and t and returns a boolean value.

2. The first line of the method checks if the length of s is not equal to the length of t. If the lengths are not equal, the method returns false because anagrams must have the same length.

3. The method creates a StringBuilder object t1 from the input string t. A StringBuilder is a mutable sequence of characters that can be modified in place.

4. The method loops through each character ch in the string s using a for-each loop over the toCharArray() method of s.

5. Inside the loop, the method checks if the string representation of the character ch is present in t1. If it is, the method removes the first occurrence of the character ch from t1 using the deleteCharAt() method of StringBuilder.

6. After looping through all the characters in s, the method checks if t1 is empty by calling the isEmpty() method of StringBuilder. If t1 is empty, it means that all the characters in t that were also present in s have been removed, so t is an anagram of s, and the method returns true. Otherwise, the method returns false.

In summary, this method determines if two strings are anagrams of each other by checking if they have the same length, looping through the characters in one string and removing them from the other string using a StringBuilder, and checking if the resulting StringBuilder is empty.

The time complexity of the given code is O(n^2), where n is the length of the input strings, due to the nested loop and the indexOf() method used inside the loop, and the space complexity is O(n) because the method creates a StringBuilder object of size n.

Third approach:

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (char ch : s.toCharArray()) {
            int val = sMap.getOrDefault(ch, 0);
            if (val != 0) val++;
            else val = 1;
            sMap.put(ch, val);
        }
        for (char ch : t.toCharArray()) {
            int val = tMap.getOrDefault(ch, 0);
            if (val != 0) val++;
            else val = 1;
            tMap.put(ch, val);
        }
        return sMap.equals(tMap);
    }        
}

Step-by-step implementation:

1. The method isAnagram takes two string inputs s and t and returns a boolean value.

2. The first line of the method checks if the length of s is not equal to the length of t. If the lengths are not equal, the method returns false because anagrams must have the same length.

3. The method creates two empty HashMap objects, sMap and tMap, to store the frequency of each character in the strings s and t, respectively.

4. The method loops through each character ch in the string s using a for-each loop over the toCharArray() method of s.

5. Inside the loop, the method retrieves the current value of the frequency of the character ch from the sMap using the getOrDefault() method of HashMap. If the value is not equal to 0, it means that the character ch has already been encountered in s, so the method increments the value by 1. Otherwise, it means that the character ch has not been encountered in s yet, so the method sets the value to 1. The method then puts the key-value pair (ch, val) in the sMap.

6. The method then loops through each character ch in the string t using a for-each loop over the toCharArray() method of t.

7. Inside the second loop, the method performs the same operations as in the first loop, but with the tMap instead of sMap.

8. After looping through both strings, the method checks if the sMap is equal to tMap using the equals() method of HashMap. If the two maps are equal, it means that the frequency of each character in s is the same as the frequency of each character in t, so t is an anagram of s, and the method returns true. Otherwise, the method returns false.

In summary, this method determines if two strings are anagrams of each other by counting the frequency of each character in both strings using HashMaps, and then comparing the two maps.

This implementation has a time complexity of O(n), where n is the length of the input strings, because it loops through each character in both strings once, and the getOrDefault() and put() methods of HashMap have a time complexity of O(1). The space complexity of this implementation is also O(n) because the method creates two HashMap objects of size n.

Conclusion:

In terms of time complexity third approach is better i.e., O(n) compared to the first and the second approaches i.e., O(n logn) & O(n^2)

Thanks for reading ....Happy Learning😁