Проверьте, есть ли строка в палиндроме: эффективность кода C #

Question

Я приехал из C фона и недавно начал писать на C #, поэтому, пожалуйста, не возражайте, если мой вопрос кажется несколько базовым.По сути, я хочу написать функцию, которая будет возвращать истину, если строка имеет палиндром, и ложь, если нет.

Строка может содержать символы, такие как пробел, ',', ':', которые я должен игнорировать.Я написал код как показано ниже

    static bool IsPalindrome(string s)
    {
        s = s.Replace(" ", "");
        s = s.Replace(",", "");
        s = s.Replace(":", "");

        int j = s.Length - 1;

        for(int i = 0; i < s.Length/2; i++)
        {
            if(s[i].ToString().Equals(s[j].ToString(),StringComparison.InvariantCultureIgnoreCase))
            {
                j--;
            }
            else
            {
                return false;
            }
        }
        return true;

    }

, где функция будет вызываться со следующей строкой

string s = "A man, a plan, a canal: Panama";

Я прочитал в документации, что в C # строка неизменна, поэтому каждый разя делаю операцию, такую ​​как replace или ToString, создается новая копия.

Так что я хотел проверить, что я).Этот код эффективен?II).Если нет, то как сделать его более эффективным.

Answer 1

Вам не нужно использовать .Replace или создавать новые строки, вы можете просто пропустить ненужные символы при сравнении.

static bool IsPalindrome(string s)
{
    var i = 0;
    var j = s.Length - 1;
    while (j > i)
    {
        if (s[i] == ':' || s[i] == ',' || s[i] == ' ')
        {
            i++;
            continue;
        }
        if (s[j] == ':' || s[j] == ',' || s[j] == ' ')
        {
            j--;
            continue;
        }

        if (char.ToUpperInvariant(s[i++]) != char.ToUpperInvariant(s[j--])) return false;
    }

    return true;
}

Answer 2

Это был бы более читабельный подход для обнаружения плаиндрома по сравнению с for loop, который вы написали:

Короткий подход, но не обязательно эффективный из-за Array.Reverse, который меняет порядок элементов:

static bool IsPalindrome(string s)
{
    s = s.Replace(" ", "");
    s = s.Replace(",", "");
    s = s.Replace(":", "");

    char[] array = s.ToCharArray();
    Array.Reverse(array);
    string backwards = new string(array);

    return s == backwards;
}

Более эффективный подход, который требует большего количества строк кодирования:

    static bool IsPalindrome(string s)
    {
        s = s.Replace(" ", "");
        s = s.Replace(",", "");
        s = s.Replace(":", "");

        int i = 0;
        int j = s.Length - 1;

        while (i < j)
        {
            if (s[i].ToString().ToLower() != s[j].ToString().ToLower())
                return false;

            i++;
            j--;
        }
        return true;
    }

Другой подход, аналогичный второму, но без необходимости преобразования char в String для сравнения:

    static bool IsPalindrome(string s)
    {
        s = s.Replace(" ", "");
        s = s.Replace(",", "");
        s = s.Replace(":", "");

        int i = 0;
        int j = s.Length - 1;

        while (i < j)
        {

            if (!char.ToLower(s[i]).Equals(char.ToLower(s[j])))
                return false;

            i++;
            j--;
        }
        return true;
    }

Answer 3

Обязательное короткое, но неэффективное решение LINQ:

static bool IsPalindrome(string s)
{
    return s.Where(Char.IsLetterOrDigit).Take(s.Length / 2)
        .SequenceEqual(s.Reverse().Where(Char.IsLetterOrDigit).Take(s.Length / 2));
}

Answer 4

Это решение должно быть знакомо вам, если вы работаете в среде Си.Нет необходимости выделять кучу новых строк;просто игнорируйте небуквенные символы.

Похоже, что нет сравнения без учета регистра значений char в .NET, поэтому этот код предполагает, что ToLower(...) с текущей культурой достаточно.

public static bool EqualsIgnoreCase(char c1, char c2)
{
    var culture = System.Globalization.CultureInfo.CurrentCulture;
    return Char.ToLower(c1, culture) == Char.ToLower(c2, culture);
}

public static bool IsPalindrome(string s)
{   
    switch (s?.Length ?? 0)
    {
        case 0:
            return false;
        case 1:
            return true;
        case 2:
            return EqualsIgnoreCase(s[0], s[1]);
        case 3:
            return EqualsIgnoreCase(s[0], s[2]);
    }

    var firstIndex = 0;
    var lastIndex = s.Length - 1;

    // todo: this probably falls on its face for a string with only non-letters
    do
    {
        while (!Char.IsLetter(s[firstIndex]))
            ++firstIndex;
        while (!Char.IsLetter(s[lastIndex]))
            --lastIndex;
        if (!EqualsIgnoreCase(s[firstIndex++], s[lastIndex--]))
            return false;

    } while (firstIndex < lastIndex);

    return true;
}