|
|
# isPalindrome
|
|
|
|
|
|
## описание задачи
|
|
|
|
|
|
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
|
|
|
|
|
|
Given a string s, return true if it is a palindrome, or false otherwise.
|
|
|
|
|
|
Example 1:
|
|
|
|
|
|
- Input: s = "A man, a plan, a canal: Panama"
|
|
|
- Output: true
|
|
|
- Explanation: "amanaplanacanalpanama" is a palindrome.
|
|
|
|
|
|
Example 2:
|
|
|
|
|
|
- Input: s = "race a car"
|
|
|
- Output: false
|
|
|
- Explanation: "raceacar" is not a palindrome.
|
|
|
|
|
|
Example 3:
|
|
|
|
|
|
- Input: s = " "
|
|
|
- Output: true
|
|
|
- Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.
|
|
|
|
|
|
|
|
|
Constraints:
|
|
|
|
|
|
- `1 <= s.length <= 2 * 105`
|
|
|
- s consists only of printable ASCII characters.
|
|
|
|
|
|
## тест кейсы
|
|
|
|
|
|
```ts
|
|
|
describe("isPalindrome", () => {
|
|
|
it("A man, a plan, a canal: Panama => true", () => {
|
|
|
expect(isPalindrome("A man, a plan, a canal: Panama")).toBeTruthy();
|
|
|
});
|
|
|
|
|
|
it("race a car => false", () => {
|
|
|
expect(isPalindrome("race a car")).toBeFalsy();
|
|
|
});
|
|
|
|
|
|
it(" _ => true", () => {
|
|
|
expect(isPalindrome(" ")).toBeTruthy();
|
|
|
});
|
|
|
|
|
|
it(" 0P => false", () => {
|
|
|
expect(isPalindrome("0P")).toBeFalsy();
|
|
|
});
|
|
|
});
|
|
|
```
|
|
|
|
|
|
## текстовое описание решения
|
|
|
|
|
|
- я заведу два указателя которые поставлю в начало и в конец и буду двигаться в цикле пока эти указатели не пересекуться
|
|
|
- в цикле я буду получать значение этих двух указателей и проверять если это буква я буду их сравнивать приведя к нижнему регистру
|
|
|
- если они равны я буду двигать указатели дальше
|
|
|
- если они не равны я буду возвращать false
|
|
|
- перед сравнением нужно проверить что оба символа у меня буквы по условию задачи
|
|
|
- если один из указателей не буква я буду двигать этот указатель пока не встречу букву
|
|
|
- для проверки буква это или нет я заведу вспомогательную функцию в которой буду текущий символ приводить к нижнему и верхнему регистру и сравнивать если их значения не равны значит это буква
|
|
|
|
|
|
## ассимптотическая оценка
|
|
|
|
|
|
| Description | Estimation |
|
|
|
| ----------- | ---------- |
|
|
|
| time: | O(n) |
|
|
|
| mem: | O(n) |
|
|
|
|
|
|
## time
|
|
|
|
|
|
| Description | Time |
|
|
|
| ------------------------------------------- | ----- |
|
|
|
| анализ и сбор информации | 04:18 |
|
|
|
| обдумываение решения и формулировка решения | 05:40 |
|
|
|
| имплементация | 10:14 |
|
|
|
| исправление ошибок | 36:12 |
|
|
|
| полное время затраченое на решение | 17:03 |
|
|
|
|
|
|
## журнал ошибок
|
|
|
|
|
|
- забыл инкрементировать и декрементировать указатели
|
|
|
- не учел числа
|
|
|
- поправил числа слетел первый кейс
|
|
|
- заменил проверку чисел на регулярное выражение
|
|
|
|
|
|
## code
|
|
|
|
|
|
### typescript
|
|
|
|
|
|
```ts
|
|
|
function isLetter(c: string) {
|
|
|
if (/\d/.test(c)) return true;
|
|
|
return c.toLowerCase() != c.toUpperCase();
|
|
|
}
|
|
|
|
|
|
function isPalindrome(s: string): boolean {
|
|
|
let L = 0;
|
|
|
let R = s.length - 1;
|
|
|
|
|
|
while (L <= R) {
|
|
|
let lChar = s[L].toLowerCase();
|
|
|
let rChar = s[R].toLowerCase();
|
|
|
|
|
|
if (!isLetter(lChar)) {
|
|
|
L++;
|
|
|
continue;
|
|
|
}
|
|
|
if (!isLetter(rChar)) {
|
|
|
R--;
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
if (lChar !== rChar) return false;
|
|
|
L++;
|
|
|
R--;
|
|
|
}
|
|
|
|
|
|
return true;
|
|
|
};
|
|
|
```
|