Matching strings

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 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?

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--;
}

StackExchange Code Review Q#98224, answer score: 4