Проверка строки на палиндром за O(n), игнорируя регистр и не-буквы
Реализуйте IsPalindrome(s), возвращающую true, когда s читается одинаково слева направо и справа налево, игнорируя регистр и любой символ, не являющийся буквой. Требования: O(n) по времени и O(1) дополнительной памяти — идите двумя указателями с обоих концов, не создавайте очищенную копию строки. "A man, a Plan!" — НЕ палиндром, а "Madam" и "" — да.
public static bool IsPalindrome(string s)
{
// ваш код здесь
return false;
}Допишите реализацию.
Два указателя l = 0 и r = s.Length - 1, идущие к центру. Пропускайте любой символ, где char.IsLetter ложно, с любой стороны, затем сравнивайте через char.ToLower; несовпадение возвращает false. Встреча в центре возвращает true. O(n) по времени, O(1) дополнительной памяти.
- ✗Строить очищенную/развёрнутую копию, что стоит O(n) памяти вместо O(1)
- ✗Сравнивать символы без приведения регистра через
char.ToLower - ✗Забыть пропускать не-буквы с ОБЕИХ сторон перед каждым сравнением
- →Как заодно учитывать цифры как значимые символы?
- →Почему пропуск не-букв внутри цикла сохраняет общую сложность O(n)?
Задача
Проверить, читается ли строка одинаково в обе стороны, игнорируя регистр и не-буквы.
public static bool IsPalindrome(string s)
{
int l = 0, r = s.Length - 1;
while (l < r)
{
if (!char.IsLetter(s[l])) { l++; continue; } // пропускаем слева
if (!char.IsLetter(s[r])) { r--; continue; } // пропускаем справа
if (char.ToLower(s[l]) != char.ToLower(s[r]))
return false;
l++;
r--;
}
return true;
}Как это работает
Два указателя стартуют с краёв и сходятся к центру. Прежде чем сравнить пару символов, каждый указатель проматывается мимо всего, что не является буквой (char.IsLetter), — так пунктуация и пробелы не влияют на результат.
Сравнение делается с приведением к нижнему регистру (char.ToLower), поэтому регистр игнорируется. Любое несовпадение сразу возвращает false. Если указатели встретились, строка — палиндром.
Каждый символ посещается не более одного раза, поэтому сложность O(n) по времени и O(1) по памяти — мы не создаём очищенную копию строки. Пустая строка проходит цикл ноль раз и корректно возвращает true.
