Find Palindromes in an array of strings in Java

Question

Hello I am trying to find the palindromes in an array of strings . I have tried the brute force method with O(n2) time complexity

 for(int i=0;i<s.length;i++) {
            for(int j=i+1;j<s.length;j++) {
                if(s[i] == reverse(s[j])) {
                    count++;
                }
            }
        }

I am looking for a solution without using hashing and with O(n) time complexity or a better time complexity .

My problem is if I am on a particular index , I have to compare the element at that index with the remaining elements .

can anyone please help me solve this questions. TIA

It would be usefull if you add what program language you are using. That way your question is faster answered. — Tenzin, Jul 24 '15 at 18:20
Isn't OP asking about an array of strings? Aren't all these answers for single strings? — somtingwong, Jul 24 '15 at 19:40
@somtingwong if that's the case, the OP can apply that method to each of the strings in the array. — ryanyuyu, Jul 24 '15 at 19:43

score 0 · Answer 1 · answered Jul 24 '15 at 18:33

You don't need to use two for-loops to get this problem done. I'd use a single one instead.

for(int i = 0; i < string.length; i++)

We'll be going over every item in that string and checking to see if the corresponding item at the end of the string is that same character. So within your for loop:

if(string.charAt(i) != string.charAt(string.length - 1 - i)
   return false;

There is no character located at string.length, so I subtracted one to get the final character of the string. I then subtracted our index so that it'll give us the "i"th character in that String both forward and backward. We can then compare them. If they're not equal, we're not looking at a palindrome and can return false immediately.

If you make it through the full for-loop without returning false, you can return true and be guaranteed to have a palindrome at this point.

AnkeyNigam · Accepted Answer · 2015-07-24T18:52:51.260

0

You can check the String as Palindrome or not in single loop , in O(n), only by iterating from both ends like compare first with last, second with second-last and so on like :-

String st1 = "RACECAR";
int flag=0;   
    for (int j=0;j<=str1.length()-1 ;j++)   
    {   
     if (st1.charAt(j)!=st1.charAt(st1.length()-j-1))   
     {   
     flag=1;   
     break;   
     }   
    }  
  if(flag==1)   
  System.out.println("String is not a palindrome");   
  else   
    System.out.println("String is a palindrome");

Output :- String is a palindrome

edited Jul 24 '15 at 18:52

answered Jul 24 '15 at 18:46

AnkeyNigam

2,810
4
15
23

My questions is I have a array of strings ["abc","cab","bba","abb"]. In this I need to find palindromes – Newbie Jul 25 '15 at 03:23
@Newbie then you need to do inside that array loop. – AnkeyNigam Jul 25 '15 at 15:13

Find Palindromes in an array of strings in Java

2 Answers2