6
\$\begingroup\$

I am having difficulty understanding the runtime and space complexity while implementing the said question.

Following is the code:

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

public class AnagaramInBigString {


private static Map<Character, Integer> frequencyMap(String str)
{
    Map<Character, Integer> source = new HashMap<Character,Integer>();
    for(int i = 0; i < str.length(); i++)
    {

        if(str.charAt(i) == ' ')
        {
            continue;
        }
        else
        {

            if(source.containsKey(str.charAt(i)))

            {
                source.put(str.charAt(i), source.get(str.charAt(i) + 1));
            }
            else source.put(str.charAt(i), 1);
        }
    }

    return source;
}


public static void main(String []args)
{
    String check= "BACDGABCDA";
    String sample = "ABCD";
    System.out.println(sample.length());

    for(int i= 0; i <= check.length() - sample.length() ; i++)
    {
        String checkSub = check.substring(i, i + sample.length());
        System.out.println(checkSub);
        System.out.println(frequencyMap(checkSub).equals(frequencyMap(sample)));
    }
}


}

Is the time complexity O(check*sample)? Space complexity is O(sample)? Also please suggest on how I can improve the efficiency of this code.

Like:

  1. I can calculate the hashmap for sample string only once instead of doing it again and again with every iteration.
\$\endgroup\$
5
\$\begingroup\$

Time and space complexity is usually represented with n and m, so O(check*sample) and O(sample) would be O(nm) and O(n).

For complexity, if m is sample, and n is check, time complexity is actually O(n(n-m)), or \$O(n^2 - m)\$, which I would say is simple O(n). Same with space complexity, as well (this I am not sure about, please correct me if I am incorrect).


Also, you have:

public class AnagaramInBigString {

and:

private static Map<Character, Integer> frequencyMap(String str)
{

One word to describe this: inconsistency. Be consistent. Either have a newline, or don't.

I suggest not have a new line, as it wastes newlines, and doesn't it make it a bit more readable. It also follows Java conventions.

This crazy code:

    if(str.charAt(i) == ' ')
    {
        continue;
    }
    else
    {

        if(source.containsKey(str.charAt(i)))

        {
            source.put(str.charAt(i), source.get(str.charAt(i) + 1));
        }
        else source.put(str.charAt(i), 1);
    }

I can't even follow it. In addition to the above suggestion, always put braces for if, for, and while statements, no matter how long or short the statements are. Result:

    if (str.charAt(i) == ' ') {
        continue;
    } else {
        if (source.containsKey(str.charAt(i))) {
            source.put(str.charAt(i), source.get(str.charAt(i) + 1));
        } else {
            source.put(str.charAt(i), 1);
        }
    }

The continue can be removed by reversing the expression:

    if (str.charAt(i) != ' ') {
        if (source.containsKey(str.charAt(i))) {
            source.put(str.charAt(i), source.get(str.charAt(i) + 1));
        } else {
            source.put(str.charAt(i), 1);
        }
    }

and the put can be simplified with ternary:

    if (str.charAt(i) != ' ') {
        source.put(str.charAt(i), source.containsKey(str.charAt(i)) ?
                source.get(str.charAt(i) + 1) :
                1);
    }

Also consider using JUnit 4 for testing.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. Is the time and space complexity correct? \$\endgroup\$ – Himanshu Verma Dec 17 '15 at 0:35
  • \$\begingroup\$ Well, not exactly. Take a look at edit, coming shortly. \$\endgroup\$ – TheCoffeeCup Dec 17 '15 at 0:35
  • \$\begingroup\$ Shouldn't space complexity be O(m) considering m is the size of "Sample" as I am only creating hash map of m size. \$\endgroup\$ – Himanshu Verma Dec 17 '15 at 1:45
  • \$\begingroup\$ @HimanshuVerma Except you are creating it n-m times. \$\endgroup\$ – TheCoffeeCup Dec 17 '15 at 1:51
  • \$\begingroup\$ Yes. I think I need to look into how to calculate space-time complexity. I am having difficulties in calculating. \$\endgroup\$ – Himanshu Verma Dec 17 '15 at 14:58

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.