3
\$\begingroup\$

I am trying to find the number of string pairs in an array that are palindromes.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class TestClass {
public static void main(String args[] ) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine();
    int N = Integer.parseInt(line);

    int count = 0;

    String s[] = new String[N];

    for (int i = 0; i < N; i++) {
        s[i] = br.readLine();                   
    }            

    for (int i = 0; i < N; i++) {
        String str = s[i];

        for(int j=i; j<N; j++) {

            StringBuilder sb = new StringBuilder(s[j]);
            if(str.equals(sb.reverse().toString())){
                count++;
            }
        }           
    }

    System.out.print(count);
}
}

Is there a more efficient way to do this?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Please declare your cross-post to avoid wasting others' time. \$\endgroup\$ – 200_success Jul 25 '15 at 5:31
4
\$\begingroup\$

Is there a more efficient way to do this?

At the moment you have an \$O(N^2)\$ algorithm as you can see from the nested loops up to N This is not as efficient as it could be.

What you should have is an \$O(N \log N)\$ or \$O(N)\$ algorithm. To achieve \$O(N)\$, you need to pass over the words just once, ideally as you read them avoiding the need for a String[]. To do this, you need to store the words in a data structure with \$O(1)\$ (at least amortized) access. e.g. a HashSet or a HashMap.

It could look like this:

start with a HashSet of words so far. initially empty.
for each word *as you read it*.
   compute its palindrome.
   remove this palidrome from the set 
   and see if it was there. i.e. Set.remove(reverse) will do this.
   if it was there you have a match
   otherwise add the word to the set.
done

Instead of three loops, you only need one.

You can see that you pass over the words just once and each operation is \$O(1)\$ with the number of words. This assumes that the words length has some natural upper bound and the length of the words doesn't matter.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd bet, he meant things like 1. N is not a good variable name according to conventions, 2. it should be more descriptive, e.g., stringCount, 3. it'd be smarter to reverse s[i] instead of s[j] as otherwise the complexity is \$N^2 \cdot L\$ where \$L\$ is the string length, etc. +++ There are many beginners here who can profit more from such step-wise advice than from a much smarter solution like yours. Sure, a complete rewrite is the way to go in this case and this makes the tiny steps irrelevant for this problem. However, it's something the OP can learn from. \$\endgroup\$ – maaartinus Jul 25 '15 at 8:39
  • \$\begingroup\$ I see nothing wrong with this answer, in any of the revisions. I'd definitely say this counts as a review. \$\endgroup\$ – Simon Forsberg Jul 25 '15 at 13:18
  • 1
    \$\begingroup\$ A note though, there's no need to use Set.remove as Set.add will return false if it was there already. \$\endgroup\$ – Simon Forsberg Jul 25 '15 at 13:20
  • 1
    \$\begingroup\$ @SimonAndréForsberg Neither do I, but Quill did (in the now removed comments), so I explained what he might have meant. +++ Without Set#remove you'll get different results in case of duplicates. It's hard to tell what's right then. \$\endgroup\$ – maaartinus Jul 25 '15 at 18:58
  • \$\begingroup\$ @maaartinus thank you. This example is clearer to me. The question was cross posted on stack over flow and I believe the OP really just wanted to know how to make the code more efficient that a broad code review. \$\endgroup\$ – Peter Lawrey Jul 26 '15 at 13:29
0
\$\begingroup\$
  1. Make 2 sets, one for reversed strings and one for normal strings.
  2. Use the retainAll() method to eliminate all the strings that aren't in both sets.
  3. Return the size of the set.
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Quill Jul 25 '15 at 5:35
  • 2
    \$\begingroup\$ Note: your choice of set will matter for performance. \$\endgroup\$ – Peter Lawrey Jul 25 '15 at 5:50
0
\$\begingroup\$
  • Uppercase variable names like N do not follow Java conventions, which is camelCase.

  • N, s and str aren't too descriptive names. I'd name them number, strings and string.

  • I'd simplify:

    String line = br.readLine();
    int N = Integer.parseInt(line);
    

    to:

    int number = Integer.parseInt(br.readLine());
    
  • I'd not create StringBuilder sb = new StringBuilder(s[j]), which is expensive, inside loops but outside and use Java clearing the string buffer after loop.

|improve this answer|||||
\$\endgroup\$

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.