4
\$\begingroup\$

LeetCode 125 requires receiving a string and checking if it is a valid palindrome. I have done this and am confident with an int and a single word, but this question requires the use a of a sentence with non-alphanumeric characters. The function must ignore non-alphanumeric characters and whitespaces.

public bool isPalindrome(string s) {

    s = System.Text.RegularExpressions.Regex.Replace(s, @"\W|_", "");

    if (s == null || s == "" || s.Length == 1 || s == " ")
    {
        return true;
    }

    for (int i = 0, j = s.Length - 1; i <= s.Length / 2  && j >= s.Length /2;i--,j++)
    {
        if (Char.ToLower(s[i]) == Char.ToLower(s[j]))
        {
            continue;
        }
        return false;
    }

    return true;
}

It is my first time ever using Regex, maybe that gives my function a performance hit? Would it be better if I could implement this without Regex?

Example inputs are: "a man, a plan, a canal: Panama" -- returns true, "race a car" -- returns false, "a man, a plan, a canal -- Panama" -- returns true. The stats on this are: Runtime 136 ms, faster than 11.75% of c# submissions.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You have a typo: i--,j++. I'd start with .Replace(s, @"[\W_]+", "").ToLower(); but I've never written C# \$\endgroup\$ – CertainPerformance Nov 14 '20 at 22:55
2
\$\begingroup\$

Disclaimer: Not a Code Reviewer

  • Your solution looks fine;
  • Overall, we would want to stay away from regular expressions in solving algorithm problems – especially easy LeetCode questions are to measure our implementation skills;
  • C# has two simple functions that would do the job of (\W|_):
public class Solution {
    public bool IsPalindrome(string s) {
        var left = 0;
        var right = s.Length - 1;

        while (left < right) {
            if (!char.IsLetterOrDigit(s[left])) {
                ++left;

            } else if (!char.IsLetterOrDigit(s[right])) {
                --right;

            } else {
                if (char.ToLower(s[left]) != char.ToLower(s[right])) {
                    return false;
                }

                ++left;
                --right;
            }
        }

        return true;
    }
}

  • We can just a bit improve the runtime, but not so much, using a more readable expression such as:

    • (?i)[^a-z0-9]+;

      • (?i) matches the remainder of the pattern based on the insensitive flag;
    • [^A-Za-z0-9]+;

public class Solution {

    public bool IsPalindrome(string s) {

        s = System.Text.RegularExpressions.Regex.Replace(s, @"(?i)[^a-z0-9]+", "");

        if (s == null || s == "" || s.Length == 1 || s == " ") {
            return true;
        }

        for (int i = 0, j = s.Length - 1; i <= s.Length / 2  && j >= s.Length / 2; i++, j--) {
            if (Char.ToLower(s[i]) == Char.ToLower(s[j])) {
                continue;
            }

            return false;
        }

        return true;
    }
}

RegEx Circuit

jex.im visualizes regular expressions:

enter image description here


Demo

If you wish to simplify/update/explore the expression, it's been explained on the top right panel of regex101.com. You can watch the matching steps or modify them in this debugger link, if you'd be interested. The debugger demonstrates that how a RegEx engine might step by step consume some sample input strings and would perform the matching process.


Happy Coding! ( •ˆ_ˆ• )

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The first solution works much better. I thought about using Char.IsLetterOrDigit but I couldn't remember the function so I tried regex. Thanks a lot. \$\endgroup\$ – stupidQuestions Nov 15 '20 at 1:14

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.