Skip to content

Commit 93e4175

Browse files
alxkmalxkm
authored
refactor: Anagrams (TheAlgorithms#5390)
1 parent 7e9cdad commit 93e4175

File tree

2 files changed

+131
-117
lines changed

2 files changed

+131
-117
lines changed

‎src/main/java/com/thealgorithms/strings/Anagrams.java

Lines changed: 91 additions & 102 deletions
Original file line numberDiff line numberDiff line change
@@ -10,141 +10,130 @@
1010
* also the word binary into brainy and the word adobe into abode.
1111
* Reference from https://en.wikipedia.org/wiki/Anagram
1212
*/
13-
public class Anagrams {
13+
public final class Anagrams {
14+
private Anagrams() {
15+
}
1416

1517
/**
16-
* 4 approaches are provided for anagram checking. approach 2 and approach 3 are similar but
17-
* differ in running time.
18-
* OUTPUT :
19-
* first string ="deal" second string ="lead"
20-
* Output: Anagram
21-
* Input and output is constant for all four approaches
22-
* 1st approach Time Complexity : O(n logn)
23-
* Auxiliary Space Complexity : O(1)
24-
* 2nd approach Time Complexity : O(n)
25-
* Auxiliary Space Complexity : O(1)
26-
* 3rd approach Time Complexity : O(n)
27-
* Auxiliary Space Complexity : O(1)
28-
* 4th approach Time Complexity : O(n)
29-
* Auxiliary Space Complexity : O(n)
30-
* 5th approach Time Complexity: O(n)
31-
* Auxiliary Space Complexity: O(1)
18+
* Checks if two strings are anagrams by sorting the characters and comparing them.
19+
* Time Complexity: O(n log n)
20+
* Space Complexity: O(n)
21+
*
22+
* @param s the first string
23+
* @param t the second string
24+
* @return true if the strings are anagrams, false otherwise
3225
*/
33-
public static void main(String[] args) {
34-
String first = "deal";
35-
String second = "lead";
36-
// All the below methods takes input but doesn't return any output to the main method.
37-
Anagrams nm = new Anagrams();
38-
System.out.println(nm.approach2(first, second)); /* To activate methods for different approaches*/
39-
System.out.println(nm.approach1(first, second)); /* To activate methods for different approaches*/
40-
System.out.println(nm.approach3(first, second)); /* To activate methods for different approaches*/
41-
System.out.println(nm.approach4(first, second)); /* To activate methods for different approaches*/
42-
}
43-
44-
boolean approach1(String s, String t) {
26+
public static boolean approach1(String s, String t) {
4527
if (s.length() != t.length()) {
4628
return false;
47-
} else {
48-
char[] c = s.toCharArray();
49-
char[] d = t.toCharArray();
50-
Arrays.sort(c);
51-
Arrays.sort(d); /* In this approach the strings are stored in the character arrays and
52-
both the arrays are sorted. After that both the arrays are compared
53-
for checking anangram */
54-
55-
return Arrays.equals(c, d);
5629
}
30+
char[] c = s.toCharArray();
31+
char[] d = t.toCharArray();
32+
Arrays.sort(c);
33+
Arrays.sort(d);
34+
return Arrays.equals(c, d);
5735
}
5836

59-
boolean approach2(String a, String b) {
60-
if (a.length() != b.length()) {
37+
/**
38+
* Checks if two strings are anagrams by counting the frequency of each character.
39+
* Time Complexity: O(n)
40+
* Space Complexity: O(1)
41+
*
42+
* @param s the first string
43+
* @param t the second string
44+
* @return true if the strings are anagrams, false otherwise
45+
*/
46+
public static boolean approach2(String s, String t) {
47+
if (s.length() != t.length()) {
6148
return false;
62-
} else {
63-
int[] m = new int[26];
64-
int[] n = new int[26];
65-
for (char c : a.toCharArray()) {
66-
m[c - 'a']++;
67-
}
68-
// In this approach the frequency of both the strings are stored and after that the
69-
// frequencies are iterated from 0 to 26(from 'a' to 'z' ). If the frequencies match
70-
// then anagram message is displayed in the form of boolean format Running time and
71-
// space complexity of this algo is less as compared to others
72-
for (char c : b.toCharArray()) {
73-
n[c - 'a']++;
74-
}
75-
for (int i = 0; i < 26; i++) {
76-
if (m[i] != n[i]) {
77-
return false;
78-
}
49+
}
50+
int[] charCount = new int[26];
51+
for (int i = 0; i < s.length(); i++) {
52+
charCount[s.charAt(i) - 'a']++;
53+
charCount[t.charAt(i) - 'a']--;
54+
}
55+
for (int count : charCount) {
56+
if (count != 0) {
57+
return false;
7958
}
80-
return true;
8159
}
60+
return true;
8261
}
8362

84-
boolean approach3(String s, String t) {
63+
/**
64+
* Checks if two strings are anagrams by counting the frequency of each character
65+
* using a single array.
66+
* Time Complexity: O(n)
67+
* Space Complexity: O(1)
68+
*
69+
* @param s the first string
70+
* @param t the second string
71+
* @return true if the strings are anagrams, false otherwise
72+
*/
73+
public static boolean approach3(String s, String t) {
8574
if (s.length() != t.length()) {
8675
return false;
8776
}
88-
// this is similar to approach number 2 but here the string is not converted to character
89-
// array
90-
else {
91-
int[] a = new int[26];
92-
int[] b = new int[26];
93-
int k = s.length();
94-
for (int i = 0; i < k; i++) {
95-
a[s.charAt(i) - 'a']++;
96-
b[t.charAt(i) - 'a']++;
97-
}
98-
for (int i = 0; i < 26; i++) {
99-
if (a[i] != b[i]) {
100-
return false;
101-
}
77+
int[] charCount = new int[26];
78+
for (int i = 0; i < s.length(); i++) {
79+
charCount[s.charAt(i) - 'a']++;
80+
charCount[t.charAt(i) - 'a']--;
81+
}
82+
for (int count : charCount) {
83+
if (count != 0) {
84+
return false;
10285
}
103-
return true;
10486
}
87+
return true;
10588
}
10689

107-
boolean approach4(String s, String t) {
90+
/**
91+
* Checks if two strings are anagrams using a HashMap to store character frequencies.
92+
* Time Complexity: O(n)
93+
* Space Complexity: O(n)
94+
*
95+
* @param s the first string
96+
* @param t the second string
97+
* @return true if the strings are anagrams, false otherwise
98+
*/
99+
public static boolean approach4(String s, String t) {
108100
if (s.length() != t.length()) {
109101
return false;
110102
}
111-
// This approach is done using hashmap where frequencies are stored and checked iteratively
112-
// and if all the frequencies of first string match with the second string then anagram
113-
// message is displayed in boolean format
114-
else {
115-
HashMap<Character, Integer> nm = new HashMap<>();
116-
HashMap<Character, Integer> kk = new HashMap<>();
117-
for (char c : s.toCharArray()) {
118-
nm.put(c, nm.getOrDefault(c, 0) + 1);
119-
}
120-
for (char c : t.toCharArray()) {
121-
kk.put(c, kk.getOrDefault(c, 0) + 1);
103+
HashMap<Character, Integer> charCountMap = new HashMap<>();
104+
for (char c : s.toCharArray()) {
105+
charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
106+
}
107+
for (char c : t.toCharArray()) {
108+
if (!charCountMap.containsKey(c) || charCountMap.get(c) == 0) {
109+
return false;
122110
}
123-
// It checks for equal frequencies by comparing key-value pairs of two hashmaps
124-
return nm.equals(kk);
111+
charCountMap.put(c, charCountMap.get(c) - 1);
125112
}
113+
return charCountMap.values().stream().allMatch(count -> count == 0);
126114
}
127115

128-
boolean approach5(String s, String t) {
116+
/**
117+
* Checks if two strings are anagrams using an array to track character frequencies.
118+
* This approach optimizes space complexity by using only one array.
119+
* Time Complexity: O(n)
120+
* Space Complexity: O(1)
121+
*
122+
* @param s the first string
123+
* @param t the second string
124+
* @return true if the strings are anagrams, false otherwise
125+
*/
126+
public static boolean approach5(String s, String t) {
129127
if (s.length() != t.length()) {
130128
return false;
131129
}
132-
// Approach is different from above 4 aproaches.
133-
// Here we initialize an array of size 26 where each element corresponds to the frequency of
134-
// a character.
135130
int[] freq = new int[26];
136-
// iterate through both strings, incrementing the frequency of each character in the first
137-
// string and decrementing the frequency of each character in the second string.
138131
for (int i = 0; i < s.length(); i++) {
139-
int pos1 = s.charAt(i) - 'a';
140-
int pos2 = s.charAt(i) - 'a';
141-
freq[pos1]++;
142-
freq[pos2]--;
132+
freq[s.charAt(i) - 'a']++;
133+
freq[t.charAt(i) - 'a']--;
143134
}
144-
// iterate through the frequency array and check if all the elements are zero, if so return
145-
// true else false
146-
for (int i = 0; i < 26; i++) {
147-
if (freq[i] != 0) {
135+
for (int count : freq) {
136+
if (count != 0) {
148137
return false;
149138
}
150139
}

‎src/test/java/com/thealgorithms/strings/AnagramsTest.java

Lines changed: 40 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,48 @@
11
package com.thealgorithms.strings;
22

3-
import static org.junit.jupiter.api.Assertions.assertTrue;
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
44

5-
import org.junit.jupiter.api.Test;
5+
import java.util.stream.Stream;
6+
import org.junit.jupiter.params.ParameterizedTest;
7+
import org.junit.jupiter.params.provider.MethodSource;
68

79
public class AnagramsTest {
810

9-
@Test
10-
public void isAlphabetical() {
11-
String input1 = "late";
12-
Anagrams anagrams = new Anagrams();
13-
assertTrue(anagrams.approach1(input1, "tale"));
14-
assertTrue(anagrams.approach1(input1, "teal"));
15-
assertTrue(anagrams.approach2(input1, "tale"));
16-
assertTrue(anagrams.approach2(input1, "teal"));
17-
assertTrue(anagrams.approach3(input1, "tale"));
18-
assertTrue(anagrams.approach3(input1, "teal"));
19-
assertTrue(anagrams.approach4(input1, "tale"));
20-
assertTrue(anagrams.approach4(input1, "teal"));
21-
assertTrue(anagrams.approach5(input1, "teal"));
11+
record AnagramTestCase(String input1, String input2, boolean expected) {
12+
}
13+
14+
private static Stream<AnagramTestCase> anagramTestData() {
15+
return Stream.of(new AnagramTestCase("late", "tale", true), new AnagramTestCase("late", "teal", true), new AnagramTestCase("listen", "silent", true), new AnagramTestCase("hello", "olelh", true), new AnagramTestCase("hello", "world", false), new AnagramTestCase("deal", "lead", true),
16+
new AnagramTestCase("binary", "brainy", true), new AnagramTestCase("adobe", "abode", true), new AnagramTestCase("cat", "act", true), new AnagramTestCase("cat", "cut", false));
17+
}
18+
19+
@ParameterizedTest
20+
@MethodSource("anagramTestData")
21+
void testApproach1(AnagramTestCase testCase) {
22+
assertEquals(testCase.expected(), Anagrams.approach1(testCase.input1(), testCase.input2()));
23+
}
24+
25+
@ParameterizedTest
26+
@MethodSource("anagramTestData")
27+
void testApproach2(AnagramTestCase testCase) {
28+
assertEquals(testCase.expected(), Anagrams.approach2(testCase.input1(), testCase.input2()));
29+
}
30+
31+
@ParameterizedTest
32+
@MethodSource("anagramTestData")
33+
void testApproach3(AnagramTestCase testCase) {
34+
assertEquals(testCase.expected(), Anagrams.approach3(testCase.input1(), testCase.input2()));
35+
}
36+
37+
@ParameterizedTest
38+
@MethodSource("anagramTestData")
39+
void testApproach4(AnagramTestCase testCase) {
40+
assertEquals(testCase.expected(), Anagrams.approach4(testCase.input1(), testCase.input2()));
41+
}
42+
43+
@ParameterizedTest
44+
@MethodSource("anagramTestData")
45+
void testApproach5(AnagramTestCase testCase) {
46+
assertEquals(testCase.expected(), Anagrams.approach5(testCase.input1(), testCase.input2()));
2247
}
2348
}

0 commit comments

Comments
 (0)