Question
Formatted question description: https://leetcode.ca/all/242.html
242 Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
Algorithm
The core point lies in the use of hash table mapping, using an array to act as the hash table.
First judge whether the two strings have the same length, if they are not the same, return false directly.
Then count the number of occurrences of all the characters in s and store them in an array of size 26, because the input string is limited to lowercase letters in the title.
Then we will count the t string again, and return false if it does not match.
Code
Java
-
import java.util.Arrays; public class Valid_Anagram { public static void main(String[] args) { Valid_Anagram out = new Valid_Anagram(); Solution2 s = out.new Solution2(); System.out.println(s.isAnagram("anagram!@#$%", "!@#$%nagaram")); } class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } char[] str1 = s.toCharArray(); // NlogN char[] str2 = t.toCharArray(); Arrays.sort(str1); Arrays.sort(str2); // direct compare return Arrays.equals(str1, str2); } } public class Solution2 { public boolean isAnagram(String s, String t) { int[] count = new int[256]; for (int i = 0; i < s.length(); i++) { // count[s.charAt(i) - 'a']++; // O(N) count[s.charAt(i) - '!']++; // O(N) } for (int i = 0; i < t.length(); i++) { // count[t.charAt(i) - 'a']--; // @note: for followup question, if use `a` then result will be -64. so use 1st unicode // or, use a valid map data structure, instead of int array count[t.charAt(i) - '!']--; } for (int i : count) { if (i != 0) return false; } return true; } } }
-
// OJ: https://leetcode.com/problems/valid-anagram/ // Time: O(N) // Space: O(C) class Solution { public: bool isAnagram(string s, string t) { int cnt[26] = {}; for (char c : s) cnt[c - 'a']++; for (char c : t) cnt[c - 'a']--; for (int n : cnt) { if (n) return false; } return true; } };
-
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ if not len(s) == len(t): return False sHash = tHash = 1 sCount = [0] * 26 tCount = [0] * 26 p1 = 2903 p2 = 29947 for i in range(0, len(s)): sCount[ord(s[i]) - ord('a')] += 1 tCount[ord(t[i]) - ord('a')] += 1 for i in range(0, 26): sHash = sHash * p1 + sCount[i] tHash = tHash * p1 + tCount[i] p1 *= p2 return sHash == tHash