Radix Sort Algorithm
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
September 10, 2020
Given two strings s and t , write a function to determine if t is an anagram of s.
Example
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Note: You may assume the string contains only lowercase alphabets.
First try to understand what an Anagram is. Its NOT about checking order of characters in a string.
Its about checking that:
A simple solution can be to sort the strings first, then compare.
public boolean isAnagram_sort(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] s1 = s.toCharArray();
char[] s2 = t.toCharArray();
Arrays.sort(s1);
Arrays.sort(s2);
return Arrays.equals(s1, s2);
}
It is equal to complexity taken by sorting.
Its O(nlogn)
Another simple solution is that we can use a HashMap<Character, Integer>
.
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<s.length(); i++) {
int count = map.getOrDefault(s.charAt(i), 0);
count ++;
map.put(s.charAt(i), count);
}
for (int i=0; i<t.length(); i++) {
int count = map.getOrDefault(t.charAt(i), 0);
if (count == 0) {
return false;
}
count --;
map.put(t.charAt(i), count);
}
return true;
}
Its O(n)
Since we know that there are only lowercase characters
. We know the unique number of characters will be 26
.
Integer array
of count 26
a
, second to b
and so on.public boolean isAnagram_array(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int count[] = new int[26];
for (int i=0; i<s.length(); i++) {
count[s.charAt(i) - 'a'] ++;
}
for (int i=0; i<t.length(); i++) {
if (count[t.charAt(i) - 'a'] <= 0) {
return false;
}
count[t.charAt(i) - 'a'] --;
}
return true;
}
Note that t.charAt(i) - 'a'
is just to manipulate our indexes.
Its O(n)
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
Problem Statement Given a string, find the length of the longest substring…
Problem Statement Given an array, rotate the array to the right by k steps…
Problem Statement Say you have an array prices for which the ith element is the…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Given a string s, find the longest palindromic substring in s…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…