Leetcode — anagram

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.

--

--

--

A software engineer that plays yu-gi-oh

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

A glance through Metal Live Filters

Microsoft Excel Features and Concepts that Everyone (Including Developers) Should Know

Unity: Creating a Main Menu

Implement your own operating system- Part 5

5 steps to pre-engineer any project!

Should developers be managers?

Writing code slower

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
yoshie

yoshie

A software engineer that plays yu-gi-oh

More from Medium

Graph Algorithm — Cycle Detection in Directed Graph using DFS

Leetcode Solutions

LC | Weekly Contest 282 | Q4 2188. Minimum Time to Finish the Race | Hard

Leetcode 169: Majority Element