The fastest method of determining if a string is a palindrome

Question

I need an algorithm that verify with the fastest possible execution time, if a string is a palindrome ( the string can be a proposition with uppercase or lowercase letter, spaces etc.). All of this in Java. I got a sample :

bool isPalindrome(string s) {
    int n = s.length();
    s = s.toLowerCase();
    for (int i = 0; i < (n / 2) + 1; ++i) {
        if (s.charAt(i) != s.charAt(n - i - 1)) {
            return false;
        }
    }
    return true;
}

I transformed the string in lowercase letter using .toLowerCase() function, but I don't know how much it affects the execution time .

And as well I don't know how to solve the problem with punctuation and spaces between words in a effective way.

Your method is as effective as all other methods that are effective. One could try to find one that is more efficient, though.... — Marco13, Jan 28 '14 at 11:05
Yea I think I that was my question actually..with "efficient" not "effective" . — Bogdan Mursa, Jan 28 '14 at 11:08
possible duplicate of [Reverse a string in Java](http://stackoverflow.com/questions/7569335/reverse-a-string-in-java) — Anders R. Bystrup, Jan 28 '14 at 11:08
@AndersR.Bystrup It's not a duplicate, but perhaps it's related. Duplicate questions must be exactly that - this asks about palindromes while that asks about reversing strings. — Duncan Jones, Jan 28 '14 at 11:09
@BogdanMursa This question is unanswerable until you can better define "effective". By what measure do you decide the best answer? Lines of code? Speed of execution? — Duncan Jones, Jan 28 '14 at 11:10
What "problem of spaces"? Should spaces be completely ignored? — maaartinus, Jan 28 '14 at 11:17

score 10 · Answer 1 · edited Jan 28 '14 at 12:08

10

I think you can just check for string reverse, not?

StringBuilder sb = new StringBuilder(str);
return str.equals(sb.reverse().toString());

Or, for versions earlier than JDK 1.5:

StringBuffer sb = new StringBuffer(str);
return str.equals(sb.reverse().toString());

edited Jan 28 '14 at 12:08

Joetjah

6,292
8
55
90

answered Jan 28 '14 at 11:05

Andrey

1,476
1
11
17

StringBuilder have one, still not the same as in the answer. – 3yakuya Jan 28 '14 at 11:09
1

@AndreyKnuppVital Haha agreed, you were at least 0.1 seconds faster! – Joetjah Jan 28 '14 at 11:13
@Joetjah: Or not. [Benchmarking is hard](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). – maaartinus Jan 28 '14 at 11:43
The expression `sb.toString()` returns `str`, so it's wasting time. – maaartinus Jan 28 '14 at 11:46
2

@AndreyKnuppVital: :D:D:D OK, I can see my reading skills could use some upgrade. – maaartinus Jan 28 '14 at 11:48
@maaartinus I wanted to reply something like that to your comment, but Andrey was at least 0.1s faster. Again. – Joetjah Jan 28 '14 at 11:49
1

@maaartinus On topic: the problem is that `String` doesn't have a `reverse()` method. If you try `str.equals(str.reverse())`, you'll get a compile error. Besides that, trying `.equals()` on StringBuilder-objects will check if they are the same reference, not if they contain the same String value. Therefore, I used `.toString()`. – Joetjah Jan 28 '14 at 11:53
1

@Joetjah: My reading skills might be even worse than I thought, but no. There's `toString` used twice. What you're saying concerns the second use. The first one just returns the original `str`. – maaartinus Jan 28 '14 at 12:03
@maaartinus 10 points for Griffondor, I've edited! Good call! – Joetjah Jan 28 '14 at 12:08

score 3 · Answer 2 · edited Dec 20 '16 at 08:42

This avoids any copying. The functions isBlank and toLowerCase are rather unspecified in your question, so define them the way you want. Just an example:

boolean isBlank(char c) {
    return c == ' ' || c == ',';
}

char toLowerCase(char c) {
    return Character.toLowerCase(c);
}

Don't worry about the costs of method calls, that's what the JVM excels at.

for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
    while (isBlank(s.charAt(i))) {
        i++;
        if (i >= j) return true;
    }
    while (isBlank(s.charAt(j))) {
        j--;
        if (i >= j) return true;
    }
    if (toLowerCase(s.charAt(i)) != toLowerCase(s.charAt(j))) return false;
}
return true;

Try to benchmark this... I'm hoping mu solution could be the fastest, but without measuring you never know.

This looks like a nice solution. +1 – Keppil Jan 28 '14 at 12:09 — Keppil, Jan 28 '14 at 12:09

score 2 · Answer 3 · answered Jan 28 '14 at 11:09

2

Your solution seems just fine when it comes to effectiveness.

As for your second problem, you can just remove all spaces and dots etc before you start testing:

String stripped = s.toLowerCase().replaceAll("[\\s.,]", "");
int n = stripped.length();
for (int i = 0; i < (n / 2) + 1; ++i) {
    if (stripped.charAt(i) != stripped.charAt(n - i - 1)) {
...

answered Jan 28 '14 at 11:09

Keppil

45,603
8
97
119

.replaceAll("[\\s.,]", "") - the "\\s" is space character ? – Bogdan Mursa Jan 28 '14 at 11:11
`\\s` is short-hand for a whitespace character: `[ \t\n\x0B\f\r]`. – Keppil Jan 28 '14 at 11:12
Ok mate, thanks. I think this is one solution on what I need. Any ideea of how much it affects the time and space efficiency ? – Bogdan Mursa Jan 28 '14 at 11:15
@BogdanMursa: Using `toLowerCase()` and the regex is most probably slower than doing it on the fly, but why does it matter? – maaartinus Jan 28 '14 at 11:19
@maaartinus what do you mean with "on the fly" – Bogdan Mursa Jan 28 '14 at 11:30
@BogdanMursa: I mean "without copying the string". You need no additional memory and if you're lucky you can exit quickly (e.g., for `a....whatever....b`) before you see the whole string. See my solution. – maaartinus Jan 28 '14 at 11:32

score 1 · Answer 4 · answered Jan 28 '14 at 11:14

1

Effective is not the same of efficient.

Your answer is effective as long you consider spaces, special characters and so on. Even accents could be problematic.

About efficiency, toLowerCase is O(n) and any regexp parsing will be O(n) also. If you are concerning about that, convert and compare char by char should be the best option.

answered Jan 28 '14 at 11:14

rdllopes

4,897
4
19
36

So a solution like @Keppil posted bellow it's the best option ? – Bogdan Mursa Jan 28 '14 at 11:17
That is s.toLowerCase().replaceAll("[\\s.,]", ""); exactly the problem that I was talking about. @maaartinus is until now the fastest solution. – rdllopes Jan 28 '14 at 11:30

score 1 · Answer 5 · answered Apr 18 '20 at 19:39

Here is my try:

public static boolean isPalindrome(String s)
 {
    int index1 = 0;
    int index2 = s.length() -1;

    while (index1 < index2)
    {
        if(s.charAt(index1) != s.charAt(index2))
        {
            return false;
        }
        index1 ++;
        index2 --;
    }
    return true;
 }

score 0 · Answer 6 · edited Aug 25 '17 at 12:44

0

In normal cases :

 StringBuilder sb = new StringBuilder(myString);
 String newString=sb.reverse().toString();
 return myString.equalsIgnoreCase(newString);

In case of case sensitive use :

StringBuilder sb = new StringBuilder(myString);
String newString=sb.reverse().toString();
return myString.equals(newString);

edited Aug 25 '17 at 12:44

Lovis

9,513
5
31
47

answered Jan 28 '14 at 11:24

Raj Kumar

402
4
9

I think the OP is looking for a case sensitive solution. – Duncan Jones Jan 28 '14 at 11:25

score 0 · Answer 7 · answered Jan 30 '14 at 02:39

Here's some insight to my way of detecting a palindrome using Java. Feel free to ask question :) Hope I could help in some way....

import java.util.Scanner;
public class Palindrome  {
   public static void main(String[]args){
      if(isReverse()){System.out.println("This is a palindrome.");}
      else{System.out.print("This is not a palindrome");}
   }
   public static boolean isReverse(){
     Scanner keyboard =  new Scanner(System.in);
      System.out.print("Please type something: "); 
      String line = ((keyboard.nextLine()).toLowerCase()).replaceAll("\\W","");
      return (line.equals(new StringBuffer(line).reverse().toString()));
   }
}

The fastest method of determining if a string is a palindrome

7 Answers7