Серія задач Leetcode на кожен день: Рішення задачі “Довжина останнього слова”

Огляд Проблеми

Дано рядок s, що складається зі слів та пробілів. Потрібно повернути довжину останні слова в рядку._

Слово — це максимальна підстрічка (безперервна непорожня послідовність символів в рядку), що складається лише з не-пробільних символів.

Приклад 1:

Вхід: s = “Hello World” Вихід: 5 Пояснення: Останнє слово — “World”, його довжина 5.

Приклад 2:

Вхід: s = “ fly me to the moon “ Вихід: 4 Пояснення: Останнє слово — “moon”, його довжина 4.

Приклад 3:

Вхід: s = “luffy is still joyboy” Вихід: 6 Пояснення: Останнє слово — “joyboy”, його довжина 6.

Обмеження:

• 1 <= s.length <= 104
• s складається лише з англійських літер та пробілів ' '.
• В рядку буде хоча б одне слово.

Основні методи JavaScript, які використовуються

1.

split() : для розділення рядка за вказаним роздільником

Як працює split? string.split(separator, [, limit])

• separator, як символ, підрядок чи регулярний вираз, і розділяє рядок там, де знаходиться роздільник
• результатом є масив підрядків

s+/) - розділяє за одним чи кількома пробілами
```

\s+ — це регулярний вираз, який відповідає одному або більше пробільним символам. Використовуючи цей вираз, ми можемо розділити рядок за пробілами та отримати масив з окремими словами в реченні.

1. filter() - для фільтрації на основі заданих критеріїв

Огляд рішення

Проблема 1: Початкове завдання полягало в тому, щоб розділити підрядки з усього речення та видалити зайві пробіли на початку, в середині та в кінці речення.

Рішення: використовуючи метод split(/\s+/) в JavaScript

Проблема 2: Як видалити порожні рядки? Рішення: використати метод filter(), щоб повернути валідні значення, що не є пустими.

Спроби вирішення

Спроба 1

/**  
 * @param {string} s  
 * @return {number}  
 */  

var lengthOfLastWord = function (s) {  
 const substring = s.split(/\s+/);  
 const fullSubstring = substring.filter(val => val !== " ");  
 const lastWord = fullSubstring[fullSubstring.length - 1];  
 const lengthOfLastWord = lastWord.length;  
 return lengthOfLastWord;  
};

Після виконання цього коду він дав неправильну відповідь, оскільки не пройшов тестовий випадок " fly me to the moon ". Очікуваний результат — 4 для слова "moon", але мій алгоритм повернув "0". З цього можна зробити висновок, що алгоритм врахував порожній рядок і повернув його довжину як 0.
Моя фільтрація порожнього рядка має проблему.

Спроба 2 — Остаточне рішення

/**  
 * @param {string} s  
 * @return {number}  
 */  

var lengthOfLastWord = function (s) {  
 const substring = s.split(/\s+/);  
 const fullSubstring = substring.filter(val => val);  
 const lastWord = fullSubstring[fullSubstring.length - 1];  
 const lengthOfLastWord = lastWord.length;  
 return lengthOfLastWord;  
};

Хоча моє попереднє рішення було переважно правильним з точки зору логіки, виникла невелика проблема, яка проявляється у певних крайніх випадках, коли рядок s завершується пробілами.

Проблеми:

Метод split(/\s+/) розділяє рядок на масив слів, збігаючись з одним або кількома пробілами. Однак:

1. Якщо рядок має трейлінгові пробіли (пробіли в кінці), наприклад, "Hello world ", то split(/\s+/) створить масив, де останнім елементом може бути порожній рядок (["Hello", "world", ""]).
   2.
   Фільтрація за допомогою filter(val => val !== " ") неправильно обробляє порожні рядки, оскільки порожній рядок ("") не є строго рівним пробілу (" ").

приклад: const s = "Hello world ";

Кроки призведуть до наступного:

1. s.split(/\s+/) → ["Hello", "world", ""]
2. substring.filter(val => val !== " ") → ["Hello", "world", ""] (без змін, оскільки порожній рядок не є " ")
3. fullSubstring[fullSubstring.length - 1] → "" (порожній рядок як останній елемент)
4. lastWord.length → 0, що є неправильним.

Виправлення:

Щоб правильно обробити це, потрібно:

1. Забезпечити видалення всіх порожніх рядків з масиву після розбиття.
2. Використовувати filter(val => val) замість filter(val => val !== " "), оскільки filter(val => val) виключає порожні рядки ("") та інші "фальшиві" значення.

Що означає val => val?

Метод filter() приймає функцію зворотного виклику, яка визначає, чи має кожен елемент масиву бути включений в результатуючий масив.
У цьому випадку val => val є скороченням для:

function(val) { return val; }

• Функція перевіряє, чи є val правдивим значенням.
• Якщо val є правдивим значенням, воно включається до масиву fullSubstring.
• Якщо val є неправдивим значенням, воно виключається з масиву fullSubstring.

Що таке "правдиві" (truthy) та "неправдиві" (falsy) значення?

У JavaScript:

• Правдиві значення — це значення, які оцінюються як true в булевому контексті. Приклади:

  • Непорожні рядки (наприклад, "hello", "world")
  • Ненульові числа (наприклад, 1, -42)
  • Об'єкти, масиви тощо.

• Неправдиві значення — це значення, які оцінюються як false в булевому контексті. Приклади:

  • "" (порожній рядок)
  • 0
  • null
  • undefined
  • NaN
  • false

Чому ця лінія корисна у вашому коді?

У контексті вашої функції lengthOfLastWord, метод s.split(/\s+/) може створювати масив, який містить порожні рядки (""), особливо коли вхідний рядок містить кілька пробілів.
Використання filter(val => val) видаляє ці порожні рядки.

Остаточне рішення:

• 59/59 тестів пройдено!**
• Часова складність: O(N) (лінійний прохід по рядку).
• Просторова складність: O(N) (розмір стеку залежить від довжини вхідних даних).
• Час виконання: 0ms.
• Пам'ять: 49.37MB.

Ключові висновки з остаточного рішення

• важливість знання регулярних виразів для розуміння, коли і де розділяти підрядки

Перекладено з: Leetcode Daily Series : Solving Length of Last Word