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;
}
}
}