Leetcode — anagram

Easy — medium

Definition

From Wikipedia, 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.

Leetcode related questions

Valid Anagram
Find Anagram Mappings
Minimum Number of Steps to Make Two Strings Anagram
Minimum Number of Steps to Make Two Strings Anagram II
Group Anagrams
Find All Anagrams in a String

Questions to ask

1. Are the two strings having the same length?
2. What is the range of possible characters?

Anagram representation

No matter what anagram question is asked, you always have two string to compare if s1 is s2 ‘s anagram.

Let’s say if the string only contains lower case letters, we can easily form the string as an integer array with fixed length = 26:

String s = "hello";
int[] str = new int[26];
for (char c : s.toCharArray()) {
  str[c-'a']++;
}
// str = [0 0 0 0 1 0 0 1 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0]

This is much faster to represent a string than using a HashMap in terms of get, put, compare:

String s = "hello";
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
  map.put(map.getOrDefault(c, 0)+1);
}

Compare

For checking if s1 is s2‘s anagram, we can simply do a constant compare over the integer array:

boolean check() {
  int[] str1 = getArray("hello"); 
  int[] str2 = getArray("olelh");
  for (int i=0;i<26;i++) {
    if (str1[i] != str[2]) return false; 
  }
  return true;
}

More often, we contain only one array, and this array stores the difference between two strings:

String str1 = "hello"; 
String str2 = "olelh";
int[] str = new int[26];
for (char c : str1.toCharArray()) {
  str[c-'a']++;
}
for (char c : str2.toCharArray()) {
  str[c-'a']--;
}

Now we know how many steps to make str1 an anagram of str2.