Проблема":
«Фраза является палиндромом, если после преобразования всех прописных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково вперед и назад. Буквенно-цифровые символы включают буквы и цифры.
Получив строку s
, вернуть true
, если это палиндром, илиfalse
в противном случае».
— — —
Решил поделиться своим решением для LeetCode 125, так как оно кажется уникальным.
Обычное решение этой проблемы, кажется, использует цикл и два указателя, чтобы проверить, равны ли первый и последний символы строки, затем 2-й и 2-й - последним, затем 3-й и 3-й - последним...
Я думал, что должен быть более простой подход.
Я решил подойти к этой проблеме концептуально. Допустимый палиндром — это фраза, в которой она зеркально отражена посередине.
Так почему бы нам не разделить строку на две половины, «перевернуть» или «перевернуть» вторую половину и посмотреть, равна ли она первой половине?
var isPalindrome = function(s) { let string = s.toLowerCase().replace(/[^a-z0-9]/g, "") // s to LowerCase. Using regex to get rid of non alphanumeric values. let middle = Math.round(string.length / 2); let left = string.slice(0, middle); // getting the left string - slicing the string from (0 to middle) let right = string.slice(string.length - middle , string.length).split("").reverse().join(""); // right string - slicing the string from (middle to string.length) // using .split("").reverse().join("") - to reverse/ mirror right side of string return(left === right) };
Согласно LeetCode, время выполнения намного быстрее, чем время выполнения моего решения, использующего цикл и 2 указателя. Он использует немного больше памяти, чем решение с двумя указателями, так как я создаю несколько новых переменных (средняя, левая, правая).
— — —
Я думаю, что временная сложность составляет O (N), где n - это длина строки, когда мы нарезаем.
Я считаю, что пространственная сложность будет O (N), где n - длина строки.
Пожалуйста, дайте мне знать, если я ошибаюсь в интерпретации сложности времени и пространства, поскольку я совершенно новичок в этом.
— — —
Обновлять:
И когда я набираю это, я понимаю, что мне не нужно находить середину строки и разбивать ее на правую и левую строки.
Я могу просто взять всю свою строку, перевернуть всю строку, посмотреть, если моя строка равна моей перевернутой строке.