Skip to content

125 Verify palindrome string ✅

Leetcode

::: tip Key points 💡

  • Palindrome
  • Double pointer :::

Description

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Explanation: In this question, we define an empty string as a valid palindrome string.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Ideas

This is a question for investigating palindrome, and it is the simplest form, that is, to determine whether a string is a palindrome.

To solve this problem, we can use head and tail double pointers,

  • If the elements of the two pointers are not the same, return false directly,
  • If the elements of the two pointers are the same, we update the head and tail pointers at the same time, looping. Until the head and tail pointer meet.

The time complexity is O(n).

Taking a palindrome like "noon" as an example, our judgment process is like this:

125.valid-palindrome-1

Take "abaa" such a string that is not a palindrome, our judgment process is like this:

125.valid-palindrome-2

::: tip Key point analysis

  • Double pointer :::

C# Solution

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace Algorithms.Simple
{
  public class Palindrome
  {
    public static bool IsPalindrome(string inputString)
    {

      if (String.IsNullOrEmpty(inputString))
      {
        return true;
      }

      var rg = new Regex(@"[^a-zA-Z0-9]");
      var charArray = rg.Replace(inputString.Trim(), String.Empty).ToLower();

      for (int i = 0, j = charArray.Length - 1; i < j; i++, j--)
      {
        if (charArray[i] != charArray[j])
        {
          return false;
        }
      }

      return true;
    }
  }
}

C# Tests

using Algorithms.Simple;
using Xunit;

namespace AlgorithmTests.Simple
{
  public class PalindromeTests
  {
    [Fact]
    public void EvaluateTrue()
    {
      Assert.True(Palindrome.IsPalindrome("A man, a plan, a canal: Panama"));
    }

    [Fact]
    public void EvaluateFalse1()
    {
      Assert.False(Palindrome.IsPalindrome("race a car"));
    }


    [Fact]
    public void EvaluateFalse2()
    {
      Assert.False(Palindrome.IsPalindrome("abb"));
    }
  }
}

JavaScript Code:

/*
 * @lc app=leetcode id=125 lang=javascript
 *
 * [125] Valid Palindrome
 */
// Only handle English characters (the title ignores uppercase and lowercase, we converted all of them to lowercase, so here we only judge lowercase) and numbers
function isValid(c) {
  const charCode = c.charCodeAt(0);
  const isDigit =
    charCode >= '0'.charCodeAt(0) && charCode <= '9'.charCodeAt(0);
  const isChar = charCode >= 'a'.charCodeAt(0) && charCode <= 'z'.charCodeAt(0);

  return isDigit || isChar;
}
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  s = s.toLowerCase();
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (!isValid(s[left])) {
      left++;
      continue;
    }
    if (!isValid(s[right])) {
      right--;
      continue;
    }

    if (s[left] === s[right]) {
      left++;
      right--;
    } else {
      break;
    }
  }

  return right <= left;
};

Complexity Analysis

-Time complexity: \(O(N)\) -Space complexity: \(O(1)\)

If you have any thoughts on this, please leave me a message. I will check the answers one by one when I have time. More algorithm routines can visit my LeetCode problem solution warehouse: https://github.com/azl397985856/leetcode. Currently it has 37K stars. You can also pay attention to my public account "Like Plus" to take you to the hard bones of algorithm.

the company

  • Ali
  • Tencent
  • Baidu
  • Bytes
  • facebook
  • microsoft
  • uber
  • zenefits