_IsPalindrome() - Check if a string is a palindrome.

[guinness]

Replaced the regular expression for stripping non-word characters from [^a-z0-9] and converting the string to lowercase, to just W. I also changed the comparison from case-sensitive to non case-sensitive.

Edited June 29, 2013 by guinness

[jchd]

Philip Hazel (author of PCRE) recommends  the following pattern for matching a palindrome, right in the PCRE pattern doc:

(?i)^\W*+(?:((.)\W*+(?1)\W*+\2|)|((.)\W*+(?3)\W*+\4|\W*+.\W*+))\W*+$

<leitmotiv>

Of course what is under W or not is a subject open to debate (another instance where UCP support is the right way to go).

</leitmotiv>

[guinness]

That's quite an awesome little regular expression.

[jchd]

Everyone interested should have a look at the pcretest.exe test suite. Thousands if not much more input/patterns exploring the darkest corners of PCRE. Some of them need a good 60-minute hour to just grasp what they do despite them being very short. Also makes a good support for student problems!

BTW playing with pcretest.exe itself is a healthy exercise for anyone. It offers a lot of options which can give you a good vision of what's under the hood of a regexp (backtracking, recursion, partial matches, etc).

[guinness]

I'm currently using this for online usage.

Edit: I will be honest I don't quite get W*+, I understand W* but what does + have to do. Need to read the PCRE docs methinks!

Edited July 5, 2013 by guinness

[jchd]

The + after the quantifier denotes a "possessive quantifier", which is part of "atomic grouping" and falls in the more general "backtracking control" features. Refer to the doc mentionned in signature for more reading.

[guinness]

The + after the quantifier denotes a "possessive quantifier", which is part of "atomic grouping" and falls in the more general "backtracking control" features. Refer to the doc mentionned in signature for more reading.

Will do. Thanks jchd.

[guinness]

Updated the functions to use the native StringReverse() function.

[guinness]

Updated code. See first post.

[BrewManNH]

Just noticed that your variable $bCaseSensitive has nothing to do with case sensitivity, and your check for it in the example for "'Was it a car or a cat I saw?" isn't right either, or at least the comment isn't. It doesn't fail because of case sensitivity, it fails because the whitespace isn't stripped from the string, and there's a question mark at one end that's not at the other. This might be closer to what you're trying to achieve.

Func _IsPalindrome($sString, $bCaseSensitive = Default)
    If Not $bCaseSensitive Then
        $sString = StringRegExpReplace($sString, '\W', '')
        Return  $sString = StringReverse($sString) ; <<<<<<<<<<<<<
    EndIf
    Return $sString == StringReverse($sString) ; <<<<<<<<<<<<<<<
EndFunc   ;==>_IsPalindrome

[guinness]

I see nothing wrong with the function. Maybe the variable could be named $bRetainNonWordChars, that's true, but then the description of the variable is pretty clear in the header, that it removes non-word characters. Do you have a suggestion of a better variable name?

Edited October 10, 2014 by guinness

[BrewManNH]

I was going by your example posted and the name you used for it.

Your line "ConsoleWrite('Was it a car or a cat I saw?: ' & _IsPalindrome('Was it a car or a cat I saw?', True) & @CRLF) ; This is a palindrome, but the case-sensitive flag has been set to True, so will return False." is the one I'm referring to. The comment says it failed because the case-sensitive flag was set to true, when in fact it failed because the reversed non-stripped string isn't the same forwards and backwards because one end has a question mark on it and there are a bunch of spaces in the wrong places. 

If it were to be rewritten so that the functionality is retained, but adds a case-sensitive flag, you could do it like this.

; #FUNCTION# ====================================================================================================================
; Name ..........: _IsPalindrome
; Description ...: Check if a string is a palindrome.
; Syntax ........: _IsPalindrome($sString)
; Parameters ....: $sString             - A string value containing the palindrome.
;                  $bRetainNonWordChars - [optional] Retain all non-word characters. Default is False.
;                  $bCaseSensitive      - [optional] Case sensitive string comparison. Default is non-case sensitive
; Return values .: Success - True
;                  Failure - False
; Author ........: guinness
; Example .......: Yes
; ===============================================================================================================================
Func _IsPalindrome($sString, $bRetainNonWordChars = Default, $bCaseSensitive = Default)
    If Not $bRetainNonWordChars Then
        $sString = StringRegExpReplace($sString, '\W', '')
    EndIf
    If $bCaseSensitive Then
        Return $sString == StringReverse($sString)
    Else
        Return $sString = StringReverse($sString)
    EndIf
EndFunc   ;==>_IsPalindrome

Just a thought.

[guinness]

OK, thanks. I will leave as is for now, since you've posted an alternative.

Edited October 11, 2014 by guinness

[guinness]

I gave in by being a little more clearer, though I don't see the need for case-sensitivity checking, as Racecar is considered a palindrome even if the last r is lower case.

Edited October 11, 2014 by guinness

[Morthawt]

This is a quick little function to check whether or not a string is a Palindrome.

Function: Optimised version.

; #FUNCTION# ====================================================================================================================
; Name ..........: _IsPalindrome
; Description ...: Check if a string is a palindrome.
; Syntax ........: _IsPalindrome($sString)
; Parameters ....: $sString                      - A string value containing the palindrome.
;                  $bRetainNonAlphaNumeric      - [optional] Retain all non-word characters. Default is False.
; Return values .: Success - True
;                  Failure - False
; Author ........: guinness
; Remarks .......: Characters are checked with the case ignored i.e. A == a and Z == z.
; Example .......: Yes
; ===============================================================================================================================
Func _IsPalindrome($sString, $bRetainNonAlphaNumeric = Default)
    If Not $bRetainNonAlphaNumeric Then
        $sString = StringRegExpReplace($sString, '\W', '')
    EndIf
    Return $sString = StringReverse($sString)
EndFunc   ;==>_IsPalindrome

Function: With custom StringReverse()

; #FUNCTION# ====================================================================================================================
; Name ..........: _IsPalindrome
; Description ...: Check if a string is a palindrome.
; Syntax ........: _IsPalindrome($sString)
; Parameters ....: $sString                      - A string value containing the palindrome.
;                  $bRetainNonAlphaNumeric      - [optional] Retain all non-word characters. Default is False.
; Return values .: Success - True
;                  Failure - False
; Author ........: guinness
; Remarks .......: Characters are checked with the case ignored i.e. A == a and Z == z.
; Example .......: Yes
; ===============================================================================================================================
Func _IsPalindrome($sString, $bRetainNonAlphaNumeric = Default)
    If Not $bRetainNonAlphaNumeric Then
        $sString = StringRegExpReplace($sString, '\W', '')
    EndIf
    
    Local Const $iChar_Length = 1
    Local $bReturn = True, _
            $i = 1, $j = StringLen($sString)
    While ($i < $j) ; Converted from this: http://marc.info/?l=php-general&m=120422082915762
        If Not (StringMid($sString, $i, $iChar_Length) = StringMid($sString, $j, $iChar_Length)) Then
            $bReturn = False
            ExitLoop
        EndIf
        $i += 1
        $j -= 1
    WEnd
    Return $bReturn
EndFunc   ;==>_IsPalindrome

Example use of Function:

Example()

Func Example()
    ConsoleWrite('Racecar: ' & _IsPalindrome('Racecar') & @CRLF)
    ConsoleWrite('String: ' & _IsPalindrome('String') & @CRLF)
    ConsoleWrite('A man, a plan, a canal, Panama: ' & _IsPalindrome('A man, a plan, a canal, Panama!') & @CRLF)
    ConsoleWrite('Palindrome: ' & _IsPalindrome('Palindrome') & @CRLF)
    ConsoleWrite('Was it a car or a cat I saw?: ' & _IsPalindrome('Was it a car or a cat I saw?', True) & @CRLF) ; This is a palindrome, but the flag has been set to True, so will return False, due to symbols being retained.
    ConsoleWrite('Elk rap song? No sparkle: ' & _IsPalindrome('Elk rap song? No sparkle') & @CRLF)
    ConsoleWrite('I saw desserts; I''d no lemons, alas no melon! Distressed was I: ' & _IsPalindrome('I saw desserts; I''d no lemons, alas no melon! Distressed was I') & @CRLF)
EndFunc   ;==>Example

 

Perhaps you can help me understand something. StringReverse($sString) This should return the string which is now reversed. As I expected in this code:

$sString = 'TBOB'
$sString = StringReverse($sString)
ConsoleWrite($sString)

However why does the following code return true or false instead of the expected string in reverse?

$sString = 'TBOB'
ConsoleWrite($sString = StringReverse($sString))

Maybe I am missing something but this defied all logic for me. I guess I am missing some nuance of AutoIt here. I would appreciate some clarification.

Edited October 12, 2014 by Morthawt

[BrewManNH]

Because you're setting $sString to the return of StringReverse, and not testing if they're equal.

[guinness]

Because it's doing case-insensitive comparison and not assignment.

Perhaps it would be best to ask in GHS.

Edited October 12, 2014 by guinness

[Morthawt]

Well I typed it here because I looked at your first example code and I was trying to figure out how something so simple was returning something unexpected (by me at least). Ok, so on a new line it is assigning the return value (the reversed string) but when used as part of another function, it is checking the values are the same and returns boolean result. I get it now. Thanks.

[guinness]

When used after a Return keyword it's not assigning anymore, but comparing. Doesn't the help file explain this?

Edited October 12, 2014 by guinness

[Morthawt]

When used after a Return keyword it's not assigning anymore, but comparing. Doesn't the help file explain this?

I never noticed it. I looked at the string reverse and it just said the return value was the reversed string, which is why I was confused why your UDF showed a boolean value. But now I understand that it is the difference between an assignation vs a comparison.