[LeetCode][242. Valid Anagram] 3 Approaches: HashMap, Sorting and Counting
By Long Luo
This article is the solution 3 Approaches: HashMap, Sorting and Counting of Problem 242. Valid Anagram.
Here shows 3 Approaches to slove this problem: HashMap, Sorting and Counting.
HashMap
is an anagram of which means that the characters in both strings appear in the same kind and number of times.
We can use two to store the characters and the number of times, then compare the keys and values.
1 | public boolean isAnagram(String s, String t) { |
Analysis
- Time Complexity:
- Space Complexity: , .
Sorting
is an anagram of is equal to “two strings sorted equal”. Therefore, we can sort the strings and first, then check whether the sorted strings are equal.
1 | public static boolean isAnagram_sort(String s, String t) { |
Analysis
- Time Complexity: , sorting needs , comparing two arrays need , so total is .
- Space Complexity: , because sorting needs space.
Counting
Since the string contains only lowercase letters, we can maintain a frequency array of length .
Traverse the frequency of the characters in the record string , minus the corresponding frequency in , if , it means that contains an extra character that is not in , just return .
1 | public boolean isAnagram_cnt(String s, String t) { |
Analysis
- Time Complexity:
- Space Complexity: , .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗