You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
* 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.[1] For example, the word anagram itself can be rearranged into nag a ram, also the word binary into brainy and the word adobe into abode. Reference from https://en.wikipedia.org/wiki/Anagram
7
+
*/
8
+
9
+
packagecom.thealgorithms.strings;
10
+
importjava.util.*;
11
+
publicclassAnagrams
12
+
{
13
+
// 4 approaches are provided for anagram checking. approach 2 and approach 3 are similar but differ in running time.
14
+
publicstaticvoidmain(Stringargs[]) {
15
+
Stringfirst ="deal";
16
+
Stringsecond ="lead";
17
+
// All the below methods takes input but doesn't return any output to the main method.
18
+
Anagramsnm=newAnagrams();
19
+
System.out.println(nm.approach2(first,second));/* To activate methods for different approaches*/
20
+
System.out.println(nm.approach1(first,second));/* To activate methods for different approaches*/
21
+
System.out.println(nm.approach3(first,second));/* To activate methods for different approaches*/
22
+
System.out.println(nm.approach4(first,second));/* To activate methods for different approaches*/
23
+
24
+
/**
25
+
* OUTPUT :
26
+
* first string ="deal" second string ="lead"
27
+
* Output: Anagram
28
+
* Input and output is constant for all four approaches
29
+
* 1st approach Time Complexity : O(n logn)
30
+
* Auxiliary Space Complexity : O(1)
31
+
* 2nd approach Time Complexity : O(n)
32
+
* Auxiliary Space Complexity : O(1)
33
+
* 3rd approach Time Complexity : O(n)
34
+
* Auxiliary Space Complexity : O(1)
35
+
* 4th approach Time Complexity : O(n)
36
+
* Auxiliary Space Complexity : O(n)
37
+
*/
38
+
}
39
+
40
+
booleanapproach1(Strings,Stringt)
41
+
{
42
+
if (s.length() !=t.length())
43
+
{
44
+
returnfalse;
45
+
}
46
+
else
47
+
{
48
+
charc[] =s.toCharArray();
49
+
chard[] =t.toCharArray();
50
+
Arrays.sort(c);
51
+
Arrays.sort(d);/* In this approach the strings are stored in the character arrays and both the arrays are sorted. After that both the arrays are compared for checking anangram */
52
+
if (Arrays.equals(c,d))
53
+
{
54
+
returntrue;
55
+
}else
56
+
{
57
+
returnfalse;
58
+
}
59
+
}
60
+
}
61
+
62
+
booleanapproach2(Stringa,Stringb)
63
+
{
64
+
if(a.length()!=b.length())
65
+
{
66
+
returnfalse;
67
+
}
68
+
else
69
+
{
70
+
intm[]=newint[26];
71
+
intn[]=newint[26];
72
+
for(charc:a.toCharArray())
73
+
{
74
+
m[c-'a']++;
75
+
}
76
+
// In this approach the frequency of both the strings are stored and after that the frequencies are iterated from 0 to 26(from 'a' to 'z' ). If the frequencies match then anagram message is displayed in the form of boolean format
77
+
// Running time and space complexity of this algo is less as compared to others
78
+
for(charc:b.toCharArray())
79
+
{
80
+
n[c-'a']++;
81
+
}
82
+
for(inti=0;i<26;i++)
83
+
{
84
+
if(m[i]!=n[i])
85
+
{
86
+
returnfalse;
87
+
}
88
+
}
89
+
returntrue;
90
+
}
91
+
}
92
+
93
+
booleanapproach3(Strings,Stringt)
94
+
{
95
+
if(s.length()!=t.length())
96
+
{
97
+
returnfalse;
98
+
}
99
+
// this is similar to approach number 2 but here the string is not converted to character array
100
+
else
101
+
{
102
+
inta[]=newint[26];
103
+
intb[]=newint[26];
104
+
intk=s.length();
105
+
for(inti=0;i<k;i++)
106
+
{
107
+
a[s.charAt(i)-'a']++;
108
+
b[t.charAt(i)-'a']++;
109
+
}
110
+
for(inti=0;i<26;i++)
111
+
{
112
+
if(a[i]!=b[i])
113
+
returnfalse;
114
+
}
115
+
returntrue;
116
+
}
117
+
}
118
+
119
+
booleanapproach4(Strings,Stringt)
120
+
{
121
+
if(s.length()!=t.length())
122
+
{
123
+
returnfalse;
124
+
}
125
+
// This approach is done using hashmap where frequencies are stored and checked iteratively and if all the frequencies of first string match with the second string then anagram message is displayed in boolean format