Valid Anagram - LeetCode Solution and Approach

 

 242. Valid Anagram - LeetCode - Easy

Solve this problem in LeetCode

Problem Description:

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

 

Constraints:

1 <= s.length, t.length <= 5 * 10^4

s and t consist of lowercase English letters.

Approach:

Two words are Anagram if frequency of each character is same in both words. So we can check if both words have the same character's frequency. We can use Map but for more optimization we will use array as input will only consist of lowercase English Letters (26).

• We will initialize Array of 26 int. The default value of each int element is 0.
• We will iterate through first word and increase value of array by 1 on character's index. And keep on iterating.
• After iterating first word, we will iterate through second word and instead of increasing, we will decrease value of array by 1 on character's index because we want to balance out positive with negative(we will get 0 if frequency of characters in both words is same). And keep on iterating.
• After iterating both words, we will iterate through Array of 26 int and return false if any element doesn't equals 0. After iterating if all elements are 0, then return true. 

JAVA:

Time Complexity : 0(n)

Space Complexity: 0(1)

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] freq=new int[26];
        for(char c:s.toCharArray())
            freq[c-'a']++;
        for(char c:t.toCharArray())
            freq[c-'a']--;
        for(int n:freq)
        if(n!=0) return false;
        return true;
    }
}

Keep Learning and Practicing with Programming Chaska !!!