4
\$\begingroup\$

Basically I solved this question on one of the competitive websites:

Given the total n number of String on first input, n input follows:

We have to find such pairs of string (i,j) such that that the inverse of j equals i.

I implemented the code below, but for larger inputs, it exceeds 1 sec. What more can I do to minimise the time complexity?

Example:

abb
bba
cca
acc
dda
dad
O/P -2

    void start(){
    Scanner s=new Scanner(System.in); 
    ArrayList<String> contained=new ArrayList<>();

    int n=s.nextInt();//n test cases follow
    s.nextLine();
    int count=0;

    while(n!=0){
        String val=s.nextLine();
        contained.add(val);


        /*To find such pairs, add the current input to a list.
         * For every input, Traverse the list and see if the
         * inverse of current string matches in the list.
         * If yes, increment counter.

         * */

        for(String current:contained)
        {
            String in;
            if(val.length()==current.length())
            { in=doReverse(val);

            if(in.equals(current))
                count++;
            }
        }

        n--;
    }

    System.out.println(count);

}

static String  doReverse(String a){
    String s="";
    for(int i=a.length()-1;i>=0;i--)
    {
        s=s+a.charAt(i);

    }
    return s;

}

I used StringBuilder to reverse a string before, then I did it manually. Are there any other ways to eliminate brute force searching? Am I taking minimal steps?

\$\endgroup\$
4
\$\begingroup\$

You can use a HashMap for your "contained" variable and check if the hash contains the current variable. This way you won't have to traverse the list second time. Since getting from hash has o(1) in comparision to this approach o(n) it will be faster.

while(n!=0) {
    String val=s.nextLine();
    contained.add(val);
    if(contained.contains(doReverse(val)) {
        count++;
    }
    n--;
}
\$\endgroup\$
  • \$\begingroup\$ Yeah it came to my mind while posting the question :D \$\endgroup\$ – joey rohan Jul 27 '15 at 14:27

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.