125. Valid Palindrome

LeetCode easy оригинал: C# #csharp #easy #leetcode #string #two-pointers

LeetCode Static

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

C# решение

сопоставлено/оригинал

public class Solution {
    public bool IsPalindrome(string s) {
        int i = 0;
        int j = s.Length - 1;
        while (i < j) {
            while (i < j && !Char.IsLetterOrDigit(s[i])) {
                i++;
            }
            while (i < j && !Char.IsLetterOrDigit(s[j])) {
                j--;
            }
            if (char.ToLower(s[i]) != char.ToLower(s[j]))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while (i < j) {
            while (i < j && !Char.IsLetterOrDigit(s[i])) {
                i++;
            }
            while (i < j && !Char.IsLetterOrDigit(s[j])) {
                j--;
            }
            if (char.ToLower(s[i]) != char.ToLower(s[j]))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
                i++;
            }
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            }

            if (
                Character.toLowerCase(s.charAt(i)) !=
                Character.toLowerCase(s.charAt(j))
            ) return false;
        }

        return true;
    }
}

JavaScript решение

сопоставлено/оригинал

var isPalindrome = function (s) {
    let i = 0;
    let j = s.length - 1;
    while (i < j) {
        while (i < j && !isLetterOrDigit(s[i])) {
            i++;
        }
        while (i < j && !isLetterOrDigit(s[j])) {
            j--;
        }
        if ((s[i] + "").toLowerCase() !== (s[j] + "").toLowerCase())
            return false;
        i++;
        j--;
    }
    return true;
};
function isLetterOrDigit(character) {
    const charCode = character.charCodeAt();
    return (
        (charCode >= "a".charCodeAt() && charCode <= "z".charCodeAt()) ||
        (charCode >= "A".charCodeAt() && charCode <= "Z".charCodeAt()) ||
        (charCode >= "0".charCodeAt() && charCode <= "9".charCodeAt())
    );
}

Python решение

сопоставлено/оригинал

class Solution:
    def isPalindrome(self, s: str) -> bool:

        i, j = 0, len(s) - 1

        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1

            if s[i].lower() != s[j].lower():
                return False

            i += 1
            j -= 1

        return True

Go решение

сопоставлено/оригинал

func isPalindrome(s string) bool {
    i := 0
    j := len(s) - 1
    for i < j {
        for i < j && !isalnum(s[i]) {
            i++
        }
        for i < j && !isalnum(s[j]) {
            j--
        }
        if tolower(s[i]) != tolower(s[j]) {
            return false
        }
        i++
        j--
    }
    return true
}

func isalnum(c byte) bool {
    return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') ||
        ('A' <= c && c <= 'Z')
}

func tolower(c byte) byte {
    if 'A' <= c && c <= 'Z' {
        return c - 'A' + 'a'
    }
    return c
}

Algorithm

1️⃣

Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода.

2️⃣

Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке.

3️⃣

Результирующий алгоритм прост:

1. Установите два указателя, один на каждом конце входной строки.

2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.

3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.

4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.

5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.