Как проверить, симметрична ли строка
Постановка задачи
Дана строка. Нужно определить, является ли она симметричной: т.е. совпадают ли её левая и правая половины. Если длина строки нечётная, центральный символ не участвует в сравнении.
Примеры:
- str = “abab” → левая половина “ab”, правая “ab” → симметрична.
- str = “madam” → длина нечётная, сравниваются “ma” и “am” → не симметрична.
- str = “madma” → сравниваются “ma” и “ma” → симметрична.
Важно: симметричность здесь не то же самое, что палиндром (палиндром читается одинаково в обе стороны). Например, “civic” — палиндром, но не симметричная по нашему определению, потому что “ci” != “ic”.
Алгоритм для проверки симметричности строки
- Найти длину строки, length.
- Вычислить midIndex:
- если length чётно, midIndex = length / 2;
- если length нечётно, midIndex = length / 2 + 1 (целочисленное деление). Центральный символ игнорируется.
- Инициализировать pointer1 = 0 и pointer2 = midIndex.
- Пока pointer1 < midIndex и pointer2 < length:
- если str[pointer1] == str[pointer2], увеличить pointer1 и pointer2;
- иначе вернуть false.
- Если все соответствующие символы совпали — вернуть true.
Сложность: время O(n), память O(1).
Примечание: сравнение идёт посимвольно; если нужна нечувствительность к регистру или игнорирование пробелов/символов пунктуации — предварительно нормализуйте строку.
Когда этот подход не подходит
- Если нужно учитывать только алфавитные символы и игнорировать пробелы/знаки — сначала отфильтруйте и нормализуйте строку.
- Если сравнение должно быть регистронезависимым — приведите к одному регистру.
- Для очень длинных строк в потоковом режиме (stream) можно сравнивать блоки, сохраняя первую половину на диске/буфере.
Альтернативные подходы
- Срезы: сравнить str[:n] == str[-n:] (в языках с поддержкой срезов), где n = length//2. Простое и читабельное.
- Хеширование: вычислить хеш первой и второй половины и сравнить хеши (полезно при многократных запросах на одних данных).
- Буферизация: считывать символы по одному и сохранять первую половину в стек/буфер, затем сравнивать при чтении второй половины.
Критерии приёмки
- Для “abab” функция возвращает true.
- Для строк нечётной длины central ignored: “madam” → false, “madma” → true.
- Пустая строка считаётся симметричной (две пустые половины).
- Однобуквенная строка считается симметричной (центральный символ игнорируется).
Мини‑шпаргалка (cheat sheet)
- midIndex = length//2 (чётная)
- midIndex = length//2 + 1 (нечётная)
- time = O(n), space = O(1)
Реализации
C++
// C++ программа для проверки симметричности строки
#include
using namespace std;
bool isSymmetrical(string str)
{
int midIndex;
int length = str.length();
if (length % 2 == 0)
{
midIndex = length / 2;
}
else
{
midIndex = length / 2 + 1;
}
int pointer1 = 0;
int pointer2 = midIndex;
while (pointer1 < midIndex && pointer2 < length)
{
if (str[pointer1] == str[pointer2])
{
pointer1 += 1;
pointer2 += 1;
}
else
{
return false;
}
}
return true;
}
int main()
{
string str1 = "abab";
cout << "String 1: " << str1 << endl;
if (isSymmetrical(str1))
{
cout << "Да, строка симметрична" << endl;
}
else
{
cout << "Нет, строка не симметрична" << endl;
}
string str2 = "madam";
cout << "String 2: " << str2 << endl;
if (isSymmetrical(str2)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;
string str3 = "madma";
cout << "String 3: " << str3 << endl;
if (isSymmetrical(str3)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;
string str4 = "civic";
cout << "String 4: " << str4 << endl;
if (isSymmetrical(str4)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;
string str5 = "khokho";
cout << "String 5: " << str5 << endl;
if (isSymmetrical(str5)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;
return 0;
} Вывод (пример):
String 1: abab
Да, строка симметрична
String 2: madam
Нет, строка не симметрична
String 3: madma
Да, строка симметрична
String 4: civic
Нет, строка не симметрична
String 5: khokho
Да, строка симметричнаPython
# Python программа для проверки симметричности строки
def isSymmetrical(s):
length = len(s)
if length % 2 == 0:
midIndex = length // 2
else:
midIndex = length // 2 + 1
pointer1 = 0
pointer2 = midIndex
while pointer1 < midIndex and pointer2 < length:
if s[pointer1] == s[pointer2]:
pointer1 += 1
pointer2 += 1
else:
return False
return True
# Тесты
for s in ["abab", "madam", "madma", "civic", "khokho"]:
print("String:", s)
print("Да, строка симметрична" if isSymmetrical(s) else "Нет, строка не симметрична")Вывод (пример):
String: abab
Да, строка симметрична
String: madam
Нет, строка не симметрична
String: madma
Да, строка симметрична
String: civic
Нет, строка не симметрична
String: khokho
Да, строка симметричнаJavaScript
// JavaScript программа для проверки симметричности строки
function isSymmetrical(str) {
var midIndex;
var length = str.length;
if (length % 2 == 0) {
midIndex = Math.floor(length / 2);
} else {
midIndex = Math.floor(length / 2) + 1;
}
var pointer1 = 0;
var pointer2 = midIndex;
while (pointer1 < midIndex && pointer2 < length) {
if (str[pointer1] == str[pointer2]) {
pointer1 += 1;
pointer2 += 1;
} else {
return false;
}
}
return true;
}
["abab", "madam", "madma", "civic", "khokho"].forEach(function(s) {
console.log("String:", s);
console.log(isSymmetrical(s) ? "Да, строка симметрична" : "Нет, строка не симметрична");
});Вывод (пример):
String: abab
Да, строка симметрична
String: madam
Нет, строка не симметрична
String: madma
Да, строка симметрична
String: civic
Нет, строка не симметрична
String: khokho
Да, строка симметричнаТестовые случаи и краевые ситуации
- Пустая строка: “” → true.
- Одна буква: “a” → true.
- Строки с пробелами: если пробелы значимы — сравниваются как обычные символы; если нет — предварительно фильтруйте.
- Юникод: при работе с многобайтовыми символами учитывайте кодировку (в некоторых языках нужно использовать функции для работы с символами, а не байтами).
Ментальные модели и советы
- Представьте строку как две купюры: если суммы (последовательности) одинаковы — симметрично.
- Для визуализации: разделите строку вертикальной линией по midIndex и сравнивайте по парам.
Быстрая проверка одним выражением (где возможно)
- В Python: s[:len(s)//2] == s[-len(s)//2:] (работает для чётной длины; для нечётной предварительно вычислите n = len(s)//2).
Резюме
- Симметричность отличается от палиндрома: здесь сравниваются левый и правый блоки симметрично.
- Алгоритм прост и эффективен: O(n) по времени и O(1) по памяти.
- Перед сравнением учитывайте требования по регистру, пробелам и допустимым символам.
Важное: при работе с вводом извне всегда уточняйте, считать ли пробелы и регистр значимыми.
Автор
Редакция
Похожие материалы
Конфиденциальность
Как удалить историю Bing AI Chat
Безопасность
2FA в Vivaldi: как включить и настроить
Руководство
Bing AI в Edge: руководство по панели
Браузеры
Vivaldi 6.0: рабочие пространства и кастомные иконки
Приложения
Bing AI в SwiftKey на Android — как включить и использовать
AI инструменты