Leetcode 242. Valid Anagram

Accepted Code

Problem Statement

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.

Test Cases

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 * 104
• s and t consist of lowercase English letters.

Approach

Two words are said to be anagrams if they have the same amount of characters. It is not at all necessary that two words have to be equal, but they must have the same character with equal frequency.

In order to check whether two words are anagrams, we can sort the two strings and check whether one word equal to the other one. Actually, we can do better instead of applying sorting to the strings. We are only concerned about the frequency and the characters. So we can have a count array of size say 26 for this problem and increment the counter array while traversing through one of the strings. Then traverse through the next string and this time just decrement the counter array for each of the characters. If the two strings are anagrams, then the final values inside the counter array will be 0, otherwise not an anagram.

Algorithm

1. Check whether two strings have the same length as a base case.
2. Initialize an array of size 26 which tracks the frequency of each character.
3. Traverse through the first string and increment the counter for each character.
4. Traverse through the second string and decrement the counter for each character.
5. Check whether any of the values inside the counter array is not zero. If not zero, then no anagram.
6. Finally, return the true if all the values are zero inside the counter array.

Time and Space Complexity

We are traversing through the two strings which must be of the same length + counter array of size 26. So our time complexity will be O(26 + n + n) where n = length of the strings.

We are making use of an array of sizes 26. So our space complexity will be O(26).

Code

Java Code

LeetCodeTopInterviewQuestions/28_Valid_Anagram.java at master ·…