How to find substring palindrome? Task from frontend job interview | LeetCode | JavaScript
HTML-код
- Опубликовано: 12 авг 2024
- Привет, друзья. У нас для вас очередная задача про палиндром. Уровень сложности на Leetcode - medium. Еще под первым видео с задачей про палиндром вы спрашивали, как найти в строке самую длинную подстроку палиндром? Ура, сегодня мы разбираем именно эту задачу.
Условия: на вход нам подается строка, на выходе наша функция должна вернуть самую длинную подстроку палиндром.
В этом видео мы с вами разберем, как решить задачу с палиндромами четной и нечетной длины, а также разберем, как оптимизировать алгоритм, чтобы сложность по памяти вышла О(1).
Также в видео я упоминал алгоритм Манакера. Про него более подробно можно почитать тут:
ru.wikipedia.org/wiki/Алгорит...
e-maxx.ru/algo/palindromes_count
Предыдущие задачи про палиндромы:
1) Задача про строку палиндром: • Решаем задачи с собесе...
2) Задача про числовой палиндром: • Числовой палиндром | Р...
Ссылка на задачу на leetcode: leetcode.com/problems/longest...
Код из видео: codepen.io/puzankov/pen/rNepe...
Как всегда, оставляйте свои решения в комментариях. А также ваши лайки и поддержку нам :)
Таймкоды:
00:00 Начало.
00:26 Уровень сложности на leetcode.
00:45 Разбираем условие задачи.
01:42 Зевнул🙂
02:29 Разбираем алгоритм решения.
05:42 Пишем код решения.
06:30 Пишем вспомогательную функцию expandFromCenter.
08:58 Находим максимальную длину палиндрома для каждого символа в строке.
10:58 Оптимизируем сложность алгоритма по памяти.
13:04 Проверяем работу алгоритма - запускаем!.
13:42 Сложность алгоритма.
14:01 Алгоритм Манакера.
14:18 Присылайте свои решения.
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
---
Музыка: Blue Wednesday - Suede
#leetcode ##задачиJS #javascript #itсобеседование
Таймкоды:
00:00 Начало.
00:26 Уровень сложности на leetcode.
00:45 Разбираем условие задачи.
01:42 Зевнул🙂
02:29 Разбираем алгоритм решения.
05:42 Пишем код решения.
06:30 Пишем вспомогательную функцию expandFromCenter.
08:58 Находим максимальную длину палиндрома для каждого символа в строке.
10:58 Оптимизируем сложность алгоритма по памяти.
13:04 Проверяем работу алгоритма - запускаем!.
13:42 Сложность алгоритма.
14:01 Алгоритм Манакера.
14:18 Присылайте свои решения.
Крутое видео
@@captain_kobi7476 Рад, что понравилось! :)
спасибо Сергей за контент, хорошо прокачался на литкоде благодаря тебе,
так и до L5 фаанга недалеко, видосы смотрятся на одном дыхании
Спасибо за такие видео. Смотрел одного английского блогера, он делал задачи с codewars, я чуть не уснул от его монотонности.
Спасибо большое за годный контент!))
Спасибо вам, очень актуально для меня сейчас)
Рад, что пригодилось! ;)
Крутое видео, спасибо большое!
Cпасибо, очень полезный разбор задачи
И Вам спасибо, что смотрите
Я понял, как работает этот алгоритм, автор молодец
Спасибо за такие полезные видео
Помогает
И Вам спасибо, что смотрите! :) Это вдохновляет)
Хороший разбор! А если не получается, то не волнуйся, если не работает. Если бы все всегда работало, у тебя бы не было работы.
Очень крутая тема с решением задач
Благодарим за поддержку!
Просто лучший!!!
thank you for your excellent content!))))
Здорово рассказано про память.
Когда решал сам перед просмотром, алгоритм использовал схожий, но работал как раз-таки с подстроками. Плюс, пришлось вставить строчку-костылек на случай отсутствия палиндромов в строке.
var longestPalindrome = function(s) {
let longestPalindrome = '';
for (let i = 0; i < s.length - 1; i++){
if (s[i] === s[i + 1]) longestPalindrome = getLongestString(longestPalindrome, getPalindrome(s, i, i + 1));
if (s[i - 1] === s[i + 1]) longestPalindrome = getLongestString(longestPalindrome, getPalindrome(s, i - 1, i + 1));
}
return getLongestString(longestPalindrome, s[0]);
};
function getPalindrome(string, start, end) {
while (string[start] && string[start] === string[end]) {
start--;
end++;
}
return string.slice(++start, end);
}
function getLongestString(string1, string2) {
if (string1.length > string2.length) return string1;
return string2;
}
Классно вышло!
Спасибо, очень интересно и полезно)
Ты прям пачками, я смотрю, задачи проходишь! Крутецки!))) Высылай решения!
@@frontendscience прости, конкретно вчера я их не решал, а смотрел в качестве развлекательного видео. Очень нравится видеть алгоритмы, которые раньше и вообразить не мог)
Спасибо за видео, очень интересное решение, даже не подумал, что так можно🤔
Кому интересно сделал примерно так (за 10-15 минут)
const input1 = 'babad' // bab aba
const input2 = 'cbbd' // bb
const input3 = 'mississippi' // ississi
const input4 = 'ac' // a c
const longestPalindrome = function (str) {
let maxCheckLength = 0
let tmp = 0
const palindrome = (text) => {
text = text.toLowerCase().trim()
return text === text.split('').reverse().join('')
}
for (let i = 0; i < str.length; i++) {
for (let j = str.length - 1; j >= 0; j--) {
if (str[i] === str[j]) {
let check = str.slice(i, j + 1)
tmp = check.length
let checkResult = palindrome(check)
if (checkResult && tmp >= maxCheckLength) {
maxCheckLength = tmp
console.log(`Result of checking string "${check}" ==== ${checkResult} with length ${maxCheckLength}`);
}
}
}
}
return 0
}
console.log(longestPalindrome(input1))
console.log(longestPalindrome(input2))
console.log(longestPalindrome(input3))
console.log(longestPalindrome(input4))
Было не просто но хоть как-то решить смог, изначально не было идей вобще но чуть глянув видео и услышав про 2 указателя подумал про два цикла и дальше делал сам, понимаю что алгоритм вышел нагруженным и в условие не попадаю но рад что смог хоть как-то сделать
const longestPalindrome = str => {
let palindromes = {};
for(let i = 0; i0;j--){
if(str[i] == str[j]){
let check = str.slice(i,1+j);
let isPalindromebool = true;
[...check].forEach((elem,index,array)=>{
elem == array[array.length - index - 1] ? elem : isPalindromebool = false;
if(index == array.length -1 && isPalindromebool == true)palindromes[check.length] = str.slice(i,1+j);
})
}
}
}
let result = Object.values(palindromes);
return result.sort((a,b)=> a-b)[0];
}
Если есть советы по тому как можно улучшить код буду рад услышать их
Теперь можно и решение посмотреть.
Благодарю за решение! Идея интересная вышла. Собираешь все возможные палиндромы. Из оптимизации я бы наверное предложил хранить максимальный найденный до этого палиндром и если на новой итерации нашелся еще длиннее то заменять его в переменной. Просто сейчас все палиндромы (и его подчасти) хранятся в объекте и это большой удар по памяти )
PS: код надо подправить. В последних 2~ строках ошибка.
вот так будет работать:
let result = Object.keys(palindromes);
return palindromes[result.sort((a,b)=> b-a)[0]];
Большой рахмат!
Ыраазы бул жакты
мой костылек на пыхе, с примерами Сергея работает, на остальном не тестил
public function testPalindromSubstring( string $title ): string
{
$title = preg_replace( '/\W/', '', strtolower( $title ) );
$start = 0;
$end = 0;
if ( strlen( $title ) expand( $title, $i, $i + 1 );
}
if ( $title[ $i + 1 ] === $title[ $i - 1 ] ) {
$expand = $this->expand( $title, $i - 1, $i + 1 );
}
if ( $expand[ 0 ] - $expand[ 1 ] >= $end - $start ) {
[ $end, $start ] = $expand;
}
}
return substr( $title, $start, $end );
}
public function expand( string $title, int $start, int $end ): array
{
while ( $start >= 0 && $end < strlen( $title ) && $title[ $start ] === $title[ $end ] ) {
$start--;
$end++;
}
$start++;
return [ $end - 1, $start ];
}
Ты лучший )
Включить в понедельник утром, в начале рабочего дня... Это было страшной ошибкой)))
🤓 ))
красава!
Что-то хорошее )
Круто
thanks
Задачу решил, но возникли интересные ситуации при отправке на leetcode.
При первой проверке результат - Runtime error, так как в дополнительной функции, которая проверяет на палиндром, я преобразовывал строку в массив и обратно.
При второй отправке оптимизировал эту функцию и leetcode зачел мое решение, но с весьма печальным результатом: Runtime: 6624 ms, faster than 5%.
Ну и, наконец, при третьей, добавил выход из цикла когда получить палиндром длиннее было уже невозможно.
Вот решение:
function longestPalindrome(str) {
let longest = null;
let maxLength = 0;
let current = "";
for (let i = 0; i < str.length; i++) {
if (maxLength >= str.length - i) break; // если длиннее строки быть не может
for (let j = i; j < str.length; j++) {
current += str[j];
if (isPalindrome(current)) {
if (current.length > maxLength) {
maxLength = current.length;
longest = current;
}
}
}
current = "";
}
return longest;
}
function isPalindrome(s) {
let half = Math.floor(s.length / 2);
for (let i = 0; i < half; i++) {
if (s[i] !== s[s.length - 1 - i]) return false;
}
return true;
}
Результат на leetcode: Runtime: 2004 ms, faster than 15.32%
Конечно, решение далеко не из быстрых получилось. Поэтому сейчас начинаю смотреть решение из видео.
Классно! Круто что сам решил! Благодарю за вариант!
Суть решения: прохожусь циклом по строке и проверяю символы слева и справа. Если равны, проверяю дальше и тд. Второй вложенный цикл for делает то же самое, только если два символа встретились подряд.
function longestPalindrome(s) {
let result = s[0];
for (let i = 0; i < s.length; i++) {
let currentStr = s[i];
let maxJ = Math.min(i + 1, s.length - i); // сколько до конца строки справа или слева
if (result.length > maxJ * 2) break; // оптимизация, чтобы меньше проверять
for (let j = 1; j < maxJ; j++) {
let left = i - j;
let right = i + j;
if (s[left] !== s[right]) break;
currentStr = s[left] + currentStr + s[right];
if (currentStr.length > result.length) {
result = currentStr;
}
}
if (s[i + 1] !== s[i]) continue;
currentStr = '';
maxJ = Math.min(i + 1, s.length - 1 - i);
for (let j = 0; j < maxJ; j++) {
let left = i - j;
let right = i + 1 + j;
if (s[left] !== s[right]) break;
currentStr = s[left] + currentStr + s[right];
if (currentStr.length > result.length) {
result = currentStr;
}
}
}
return result;
}
На leetcode: Runtime: 105ms (Beats 59.34%). Решение из видео чуть быстрее: Runtime 100 ms.
что-то хорошее
Увидел условия стало как-то не по себе, нус будем пробовать
Успехов! Присылай потом решение!
Вау
Что-то хорошее
Спасибо за поддержку
мне помогло)
Рад, что было полезно!
Это решение с ЛитКода, а я вот слышал, что можно решить через хеши и бинпоиск, вы знаете о таком алгоритме?
Это мое решение) На Литкод я беру само условие задачи.
Не слышал и пока не представляю, как именно эту задачу можно решить через хеши и бинарный поиск. Бинарный поиск это поиск одного конкретного элемента, а нам необходимо найти подстроку, которая является палиндромом.
@@frontendscience Здравствуйте! Тут идея про хеши и бин поиск в следующем: есть функция, у которой аргументы такие же, как и у Вашей expandFromCenter, только мы не проходимся циклом while, а используем бин поиск для нахождения самого длинного палиндрома, только я не совсем понимаю, как использовать хеши. Прикреплю псевдокод этой функции(тут она ищет кол-во палиндромов):
int binarySearch(s : string, center, shift : int):
//shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1
int l = -1, r = min(center, s.length - center + shift), m = 0
while r - l != 1
m = l + (r - l) / 2
//reversed_hash возвращает хэш развернутой строки s
if hash(s[center - m..center]) == reversed_hash(s[center + shift..center + shift + m])
l = m
else
r = m
return r
Дякую
1:54 - ваааааа, я ровно так же делаю, когда надо резко вернуть фокус
)))) бро)
Сергей, а не могли бы указать, какие структуры данных необходимо 100% знать фронтенд-разработчику? И что делать, если прочитал условие задачи, но нет каких-то мыслей с чего начать решать, т.е. по сути нет идеи? Откуда брать это понимание, какой алгоритм нужно использовать?
Олтичная идея для новго видео! :)
Для фронтендера точно важно знать: строки, числа, объекты, массивы, сеты и мапы. Так как с этими структурами прийдется работать.
А вот для прохождения суровых собеседований в большие компании понадобится знания еще таких структур: linked list, binary tree, graph, trie, stack, queue, min/max stack.
Что касается самого алгоритма - то тут нужна практика. Надо начинать с задач попроще и повышать уровень сложности постепенно. С практикой прийдет понимание когда какой алгоритм использовать.
Если есть задача которую не получается совсем решить - можно поискать решение (даже если на другом языке программирования будет) и просто посмотреть сам алгоритм. Но потом обязательно надо повторить самому и написать работающее решение.
Попробуй объяснить человеческим языком самому себе как бы ты это сделал как человек, чисто логически. Или уточке на утином) Разбей на подзадачи, совсем простые. Затем по пунктам приступай реализовывать уже в коде. И гугли по мере незнания конкретные моменты. Скорее всего идеи как написать нет на один маленький и совершенно определённый пункт подзадачи, который можно погуглить и применить к своему алгоритму решения.
Сначала будут выходить не очень быстрые и не самые изящные решения. Но по мере тренировки будешь уже видеть, что ага, с таким ты уже сталкивался и это можно покрутить так и сяк. И так найдёшь решение. Главное не останавливаться и не бросать
4 утра это ж середина рабочего дня разве нет? о_О XD
😂
А что делать, если надо найти не подстроку палиндром, а подпоследовательность, т е можно удалять символы в середине, лишь бы был палиндром?)
Вот такое есть(Не мое):
function longest_palindrome(s) {
var max = '';
for (var i = 0; i < s.length; i++) {
for (var j = 0; j < 2; j++) {
var left = i;
var right = i + j;
while (s[left] && s[left] === s[right]) {
left--;
right++;
}
if ((right - left - 1) > max.length) {
max = s.substring(left + 1, right);
}
}
}
return max;
}
Ну алгоритм точно такой же - просто немного по другому реализован. Я специально вынес часть кода в отдельную функцию и сделал 2 переменные len1 и len2 чтобы было проще понять. По времени сложность алгоритма та же, а вот по памяти тут O(n) так как хранится вся подстрока.
А теперь присылай свое решение ;)
@@frontendscience
пока нос еще (у меня) не дорос. Понять что написано могу , но написать еще нет ... Доработать , подкорректировать
На codwerse эта задача 4 ku уровня .Из 4 уровня удалось решить пока 3 задачи.
Почему при вводе hellow вывод llo
вывод ll
А как программа понимает что мы хотим от аргументов L, R ? Как она понимает, что под L и R мы подразумеваем указатель лево и право в строке ?
Мы ведь сами задаем индексы элементов для этих указателей. Для L мы задаем индекс элемента слева, а для R - индекс элемента справа.
@@frontendscience да но как мы задаём программе, что L это левый указатель, а R это правый ? В функции написано только что L >= 0, а R < s.length. Тоесть мы просто говорим программе что L меньше или равняется 0 и что R меньше длины s. Но мы не как не объясняем программе что L и R это правый и левый указатель в массиве и что они значат
Мы вызываем функцию expandFromCenter и передаем в нее уже готовые L и R указатели в качестве аргументов. (Строки 11 и 12). Дальше на каждой итерации Левый указатель бежит в лево пока не дойдет до начала, а правый бежит вправо - пока не дойдет до конца массива (это если элементы равны друг другу на каждой итерации).
@@frontendscience тоесть мы сначала пишем функцию expandFromCenter для указателей L и R, а позже ее подключаем к len1 и len 2 ?
@@das8434 да именно так!
спать очень важно для мозга)
- Вы хорошо высыпаетесь?
- Куда?
- Доктор, это что вы мне такое классное дали?
- Поспать!
Недосмотрев до конца, считал, что знаю алгоритм Манакера... недолго я прожил во лжи
Смешно шутите :)
проверь на "ааа"
не работает
Смешно! А сам че не проверил? Ты удивишься - ведь все таки работает!
блин сложно..
Рекомендую, если еще не видели предыдущие 2 задачи про палиндромы начать именно с них. Тогда эта станет понятней.
На будущее я планирую снять еще видео с алгоритмом 2 указателя - думаю это поможет лучше разобраться и с это задачей тоже.
@@frontendscience Спасибо большое, сейчас посмотрю! А так задача очень полезная, хотелось бы ее осмыслить
@@alexey731 Ну надеюсь я в видео все подробно разобрал, и что прийдет осмысление после просмотра предыдущих. :)
Помогите тупому учиться. ) я второй день не догоняю , как у нас передается в функции expandFromCenter наша середина, если у нас итерируется одни и те же элементы , так как мы передаем их через i . то есть L=0, R=0 и так далее. , почему к примеру в слове "babad" начинает while Отрабатывать именно на середине , если у нас и до середины элементы получается одинаковые a=a ..
как я понял, expandFromCenter не начинает с середины, а с самого начала. потому что цикл for начинает i с нуля. а дальше i прибавляется. а R++ и L- -. и таким образом дальше идет. Непонятно почему он в слове babad середину показывает. там же i с нуля идет. ну да ладно
@@react_js так там услвоие L >= 0, если L === 0, то L-- это -1, что соотвественно прервет цикл while
отец, ты спишь вообще?
Я как медведь - накапливаю!
если ты смотришь это сообщение то пожалуйста оставь свое мнение об этом решение мне очень интересно
const longestPalindrome = function(s){
let str = '';
let arr = [];
let res = []
for(let i = 0; i < s.length; i++) {
str = s[i];
for(let j = i+1; j < s.length; j++) {
str += s[j]
if(isPalindrome(str)) {
arr.push(str)
}
}
}
arr.sort((a,b) => b.length - a.length);
if(!arr.length) return s[0]
// for(let i = 0; i < arr.length; i++) {
// if( arr[0].length === arr[i].length ) {
// res.push(arr[i])
// }
// }
return arr[0]
};
function isPalindrome(s) {
return s === s.split('').reverse().join('')
}
что-то хорошее
Что-то хорошее
Благодарю! )