Skip to content

reducing complexity to linear complixity #2087

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Feb 21, 2021
Merged

reducing complexity to linear complixity #2087

Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
6e135dd
reducing complexity to linear complixity
Itayventura Jan 14, 2021
d3827aa
reducing complexity to linear
Itayventura Jan 14, 2021
2ed7dd2
update CheckAnagrams algo
yanglbme Feb 21, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
64 changes: 42 additions & 22 deletions strings/CheckAnagrams.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,32 +1,52 @@
package strings;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
* Two strings are anagrams if they are made of the same letters arranged differently (ignoring the
* case).
*/
public class CheckAnagrams {
public static void main(String[] args) {
assert isAnagrams("Silent", "Listen");
assert isAnagrams("This is a string", "Is this a string");
assert !isAnagrams("There", "Their");
}
public static void main(String[] args) {
assert isAnagrams("Silent", "Listen");
assert isAnagrams("This is a string", "Is this a string");
assert !isAnagrams("There", "Their");
}

/**
* Check if two strings are anagrams or not
*
* @param s1 the first string
* @param s2 the second string
* @return {@code true} if two string are anagrams, otherwise {@code false}
*/
public static boolean isAnagrams(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
char[] values1 = s1.toCharArray();
char[] values2 = s2.toCharArray();
Arrays.sort(values1);
Arrays.sort(values2);
return new String(values1).equals(new String(values2));
}
/**
* Check if two strings are anagrams or not
*
* @param s1 the first string
* @param s2 the second string
* @return {@code true} if two string are anagrams, otherwise {@code false}
*/
public static boolean isAnagrams(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
Map<Character, Integer> charAppearances = new HashMap<>();

for (int i = 0; i < l1; i++) {
char c = s1.charAt(i);
int numOfAppearances = charAppearances.getOrDefault(c, 0);
charAppearances.put(c, numOfAppearances + 1);
}

for (int i = 0; i < l2; i++) {
char c = s2.charAt(i);
if (!charAppearances.containsKey(c)) {
return false;
}
charAppearances.put(c, charAppearances.get(c) - 1);
}

for (int cnt : charAppearances.values()) {
if (cnt != 0) {
return false;
}
}
return true;
}
}