0
\$\begingroup\$

Looking for some advice on whether or not this can be improved in terms of efficiency and speed, it would need to work on large data sets.

public class Anagrams {

    public static boolean isAnagram(String str1, String str2) {  
    String s1 = str1.replaceAll("\\s", "");  
    String s2 = str2.replaceAll("\\s", "");  
    boolean status = true;  
    if (s1.length() != s2.length()) {  
        status = false;  
    } else {  
        char[] ArrayS1 = s1.toLowerCase().toCharArray();  
        char[] ArrayS2 = s2.toLowerCase().toCharArray();  
        Arrays.sort(ArrayS1);  
        Arrays.sort(ArrayS2);  
        status = Arrays.equals(ArrayS1, ArrayS2);  
    }  
    if (status) {  
        return true; 
    } else {  
        return false; 
    }  
    }  


    public static String searchAnagram(String[] array)
    {

        String anagramsList = "";
        Arrays.sort(array, (str1, str2) -> str1.length() - str2.length());
        for(int i=0;i<(array.length -1); i++)
        {
            int j=0;
            while(array[i].length() == array[i+j].length())
            {

                if(isAnagram(array[i],array[i+j]))
                {
                    anagramsList += (array[i] + " " + array[i+j] + ", ");
                    System.out.println(array[i] + " " + array[i+j] + ", ");
                }
                j++;
            }

        }
        if(anagramsList == "")
        {
            anagramsList = "No anagrams foud";
        }
        return anagramsList;
    }

}
\$\endgroup\$
  • \$\begingroup\$ What's the intention behind String s1 = str1.replaceAll("\\s", "");, to remove all whitespace? \$\endgroup\$ – domsson Jan 20 at 10:18
2
\$\begingroup\$

In isAnagram one should start local variables with a small letter (just a convention). Do not use if-else to return a boolean.

public static boolean isAnagram(String str1, String str2) {
    String s1 = str1.replaceAll("\\s", "");
    String s2 = str2.replaceAll("\\s", "");
    boolean status = true;
    if (s1.length() != s2.length()) {
        status = false;
    } else {
        char[] arrayS1 = s1.toLowerCase().toCharArray();
        char[] arrayS2 = s2.toLowerCase().toCharArray();
        Arrays.sort(arrayS1);
        Arrays.sort(arrayS2);
        status = Arrays.equals(arrayS1, arrayS2);
    }
    return status;
}

However if you think of an anagram as a form of sorted string, one could introduce either a type Anagram, or - here - a function deriving such a sorted string: here canonicalForm.

public static boolean isAnagram2(String str1, String str2) {
    return canonicalForm(str1).equals(canonicalForm(str2));
}

public static String canonicalForm(String s) {
    String cleaned = s.replaceAll("\\s", "");
    char[] chars = cleaned.toLowerCase().toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

Most important searching for anagrams can use a map from canonical value to string(s). For ease of mapping to the original algorithm. the mapped-to value is a concatenation of anagrams:

public static String searchAnagram(String[] strings) {
    Map<String, String> canonicalToValue = new HashMap<>();
    for (String s : strings) {
        s = s.replace('\t', ' '); // Omit tabs, reserve them for our usage.
        String canonical = canonicalForm(s);
        canonicalToValue.merge(canonical, s, (oldS, s) -> oldS + "\t" + s);
    }
    return canonicalToValue.values().stream()
            .filter(s -> s.contains('\t'))                
            .collect(Collectors.joining(", "));
}

I use a tab (\t) as it seems that spaces might occur in strings. One could also use a slash (" / ").

Better yet would be to return a List<String> of anagrams, and keep a List<String> or Set<String> as map value. A TreeSet<String> would remove duplicates and is sorted.

Instead of isAnagram one only needs canonicalForm (better anagramForm?).

The complexity is reduced in code complexity, faster. Your attempt to optimize sorting on length is just a partial optimizing, needing extra checks / not fitting entirely. By using a HashMap on the canonical form of a string, one has exactly an immediate search result.

The solution could give "malmodera malordema marmelado melodrama, gasometro gasometro somertago".

No result as String would better be an empty String. Again a List seems more usable.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

You have used sorting which has a time complexity of O(nlogn)

You can use HashMap ,by which time complexity of program would be reduced to O(n)..Below is the code

static boolean areAnagram(String str1, String str2) 
    { 
  
        HashMap<Character, Integer> hmap1 
            = new HashMap<Character, Integer>(); 
        HashMap<Character, Integer> hmap2 
            = new HashMap<Character, Integer>(); 
  
        char arr1[] = str1.toCharArray(); 
        char arr2[] = str2.toCharArray(); 
  
        
        for (int i = 0; i < arr1.length; i++) { 
  
            if (hmap1.get(arr1[i]) == null) { 
  
                hmap1.put(arr1[i], 1); 
            } 
            else { 
                Integer c = (int)hmap1.get(arr1[i]); 
                hmap1.put(arr1[i], ++c); 
            } 
        } 
  
        
        for (int j = 0; j < arr2.length; j++) { 
  
            if (hmap2.get(arr2[j]) == null) 
                hmap2.put(arr2[j], 1); 
            else { 
  
                Integer d = (int)hmap2.get(arr2[j]); 
                hmap2.put(arr2[j], ++d); 
            } 
        } 
  
        if (hmap1.equals(hmap2)) 
            return true; 
        else
            return false; 
    } 

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ No need to transform the strings into character arrays, just use the method charAt() of String. Don't use get() twice on the maps. Don't cast to int but use Integer. Don't repeat code writing to the maps. Don't use if at the end, just return hmap1.equals(hmap2). \$\endgroup\$ – RoToRa Jan 20 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.