This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 36th day 🎈!
🚀 Algorithm 🚀

🌲 Verify the palindrome string

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

In this case, we define an empty string as a valid palindrome string.

Example 1:

Input:"A man, a plan, a canal: Panama"Output:trueExplanation:"amanaplanacanalpanama"It is palindrome listCopy the code

Example 2:

Input:"race a car"Output:falseExplanation:"raceacar"Not a palindrome stringCopy the code

Tip:

  • 1 <= s.length <= 2 * 10^5
  • The string S consists of ASCII characters

🌻C# method: double pointer

Thinking analytical

Double Pointers are used to traverse and align from both ends of the string to the middle, skipping non-numeric or alphabetic items.

Code:

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        int[][] dp =new int[numRows][];
        for(int i = 0; i<numRows; i++) { dp[i] =new int[i+1];
            for(int j = 0; j<=i; j++) {if(j==0 || j ==i)
                {
                    dp[i][j] = 1;
                }
                else
                {
                    dp[i][j] = dp[i- 1][j- 1] + dp[i- 1][j];
                }
            }
        }

        IList<IList<int>> p = new List<IList<int> > ();for(int i = 1; i<= numRows; i++) {var list = dp[i- 1].ToList();
            p.Add(list);
        }
        
        returnp; }}Copy the code

The execution result

By execution time:212Ms, in all CBeat 31.47% of users in # commitMemory consumption:25.9MB, in all CBeat 52.99% of users in # commit
Copy the code

🌻Java Method 1: Filter + judge

Thinking analytical

The easiest way to do this is to iterate over the string S once, reserving the alphanumeric and numeric characters in another string, sgood. So we just need to determine if sgood is a normal palindrome string.

There are two ways to judge. The first is to use the string flipping API of the language to get the reverse string sgood_rev for sgood, which is a palindrome string as long as the two strings are the same.

Code:

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        returnsgood.toString().equals(sgood_rev.toString()); }}Copy the code

The execution result

By execution time:5Ms, beat out all Java commits32.73% user memory consumption:38.4MB, beat out all Java commits76.12% of the userCopy the code

Complexity analysis

Time complexity: O (| | s), including ∣ s ∣ is the length of the string s. Space complexity: O (| s |), because we need to put all the letters and numeric characters in another string, in the worst case, the new string sgood as the original string s are exactly the same, so you need to use O (∣ s ∣) space.Copy the code

🌻Java method 2: Double-pointer the original string

Use a double pointer to the string s.

When you move one pointer, you keep moving in the direction of the other pointer until you encounter an alphabetic or numeric character, or until the two Pointers overlap.

That is, each time we move the pointer to the next alphanumeric or numeric character, we determine whether the two Pointers point to the same character.

Code:

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
            while(left < right && ! Character.isLetterOrDigit(s.charAt(left))) { ++left; }while(left < right && ! Character.isLetterOrDigit(s.charAt(right))) { --right; }if (left < right) {
                if(Character.toLowerCase(s.charAt(left)) ! = Character.toLowerCase(s.charAt(right))) {return false; } ++left; --right; }}return true; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits98.39% user memory consumption:38.7MB, beat out all Java commits21.96% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1 )
Copy the code

💬 summary

  • Today is the thirty-sixth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!