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?
