Matching strings

Question

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?

Answer 1

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

• joey rohan: Yeah it came to my mind while posting the question :D