Given two strings s and t, return true if t is an anagram of s, and false otherwise.
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.
Example 1:
Input: s = "anagram", t = "nagaram" Output: true
Example 2:
Input: s = "rat", t = "car" Output: false
There are a few ways to solve this problem. I am not going to post the code since It is not really necessary. The important thing to know is to what approach to take and how to solve it, rest can be done by learning syntax of any language.
Full source code of solution in C++ : Anagram.cpp
Definition: Two strings are anagrams if they are made of the same characters with the same frequencies.
Pseudocode:
length (string1 != string2) -> Not anagrams
freq1 = frequencies of characters of String1
freq2 = frequences of characters of String2
if freq1 == freq2
Strings are anagrams
Approach #1 - HashMap
This is perhaps the best approach to solve the problem. You can use HashMap data structure in order to solve this problem. When there are finite amount of characters in a string, It is easier to sort and compare the string, but It is seldom the case in real world scenario. A string can contain any characters, so HashMap is the best way to solve this problem.
HashMap internally saves each unique characters as keys. It internally avoids duplication of characters and keeps track of each unique characters and we can assign a value of occurrence as we find duplicate characters.
For example, if you have input string1="salesmen" and string2="nameless",
you get the following HashMap,
Freq1 = { Freq2 = {
s = 2, n = 1,
a = 1, a = 1,
l = 1, m = 1,
e = 2, e = 2,
m = 1, l = 1,
n = 1 s = 2,
} }
Since HashMap key and value pair of "salesmen" and "nameless" are equal, these strings are anagrams.
In this approach, you simply have to iterate through all individual characters in each string and then add each character as KEY in HashMap. If that KEY (character) already exists in the HashMap, then increment VALUE of that KEY by 1 to keep track of how many times a single unique character appears in the string. Once that is done, you can simply check if two maps are equal. If they are then strings are anagrams.
So, for example, if S occurs two times,
Then hash map will have following representation...
S (key) = 2 (value)
Approach #2 - Sorting
Two anagrams have the same lexicographical sorted string. So in this approach, you can first sort both strings and then compare those two.
For example,
String1 = "nameless"
String2 = "salesmen"
Sorted("nameless") = "aeelmnss"
Sorted("salesmen") ="aeelmnss"
So since both sorted strings are same, they are anagrams.
In simplest code, it can be written as follows:
bool areAnagramUsingSort(string str1, string str2) {
//get lengths of both strings
int l1 = str1.length();
int l2 = str2.length();
if(l1 != l2){
return false;
}
sort(str1.begin(), str2.end());
sort(str2.begin(), str2.end());
for (int i =0; i < l1; i++) {
if(str1[i] != str2[i])
return false;
}
return true;
}
Approach #3 - Without sorting or Hashmap
In this approach, you have to assume that all standard ASCII characters are used in strings. Total number of characters available in ASCII is 256. You can create an array of 256 int values. When strings are anagrams, you can use elimination approach because equal amount of characters are in both strings.
For example, string1="aabc" and string2="baca"
You can create this table and default value is 0 for each character.
String1 (addition +1) String2 (substration -1)
a = 1 b = -1
a = 1+1= 2 a = 2-1 = 1
b = -1+1=0 c= -1
c = -1+1 =0 a = 1-1 =0
So as you can see, after elimination a,b,c all have 0 value in the end, thus the strings are anagrams.
Steps: Input string1="aaca" and string2="acaa"
- Create an array of int with size of 256 with all values by default 0.
- Iterate through strings, i, 0..4
- array[string1] ... flip default 0 value in array to 1
- array[string2] .. flip value by -1..
- if both strings are anagrams, then the value would remain 0, else 1 or -1
- if array remains with all zero after eliminating and adding, it means both strings are anagrams.
#define TOTAL_CHARS 256
bool bruteForceAnagrams(string str1, string str2){
int count[TOTAL_CHARS] = {0}; //initializes an array of 256 ints with 0s.
int i;
//anagram - nagaram
// str1[i] && str2[i] = checks if there's some value in both.
for(i=0; str1[i] && str2[i]; i++){
count[str1[i]]++;
//cout << count[str1[i]] << endl; // to debug / understand
count[str2[i]]--;
//cout << count[str2[i]] << endl; // to debug/understand
}
if(str1[i] || str2[i]){
return false;
}
for(i = 0; i< TOTAL_CHARS; i++){
/*This will check based on 0 or 1. 1 being true, 0 being false, so if theres 1, it will execute to return false.*/
if(count[i])
return false;
}
return true;
}Please check my comments and run this code to really understand the logic.
So these three are the best approaches to solve this problem. There are other ways as well which you can try but using data structure like hashmap, really makes this problem time efficient and easier as well.
Here are the full code of solutions that I tried in Kotlin and C++. You should always first try to implement solution from the theory/ pseudocode first by yourself and then look at the solution to look for ways to improve your solution.
Full source code of solution in Kotlin: Anagrams.kt
0 Comments