LeetCode: 58 Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is a maximal substring consisting of non-space characters only.

Example

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

问题

给定一个由单词和空格组成的字符串 s，返回字符串中最后一个单词的长度。一个单词是由非空格字符组成的最长子字符串。

例子

输入: s = "Hello World"
输出: 5
解释: 最后一个单词是 "World"，长度为 5。

输入: s = "   fly me   to   the moon  "
输出: 4
解释: 最后一个单词是 "moon"，长度为 4。

输入: s = "luffy is still joyboy"
输出: 6
解释: 最后一个单词是 "joyboy"，长度为 6。

Iterative Solution

Approach: Trim and Reverse / 修剪和反转

To find the length of the last word in a string, we can first remove any trailing spaces (if any), then count the length of the last word by iterating through the string from the end until the first space is encountered.

Approach Explanation / 方法解释

Trim Trailing Spaces: First, remove any trailing spaces from the string to ensure we start from the last word.
Find Last Word: Iterate from the end of the string and count the characters until a space is found, which marks the end of the last word.

Iterative Algorithm / 迭代算法

Trim the string to remove any trailing spaces.
Start from the end of the string and count characters until a space or the start of the string is found.
Return the length of the last word.

Iterative Implementation / 迭代实现

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        # Trim trailing spaces
        s = s.strip()

        # Initialize length of the last word
        length = 0

        # Iterate from the end of the string
        for i in range(len(s) - 1, -1, -1):
            if s[i] == ' ':
                break
            length += 1

        return length

Iterative Solution Explanation / 迭代解决方案解释

Trim Trailing Spaces / 修剪尾部空格
```
s = s.strip()
```
- English: Remove any trailing spaces from the string to ensure we start from the last word.
- Chinese: 删除字符串末尾的空格，确保我们从最后一个单词开始处理。
Iterate from the End of the String / 从字符串的末尾开始迭代
```
for i in range(len(s) - 1, -1, -1):
   if s[i] == ' ':
       break
   length += 1
```
- English: Start iterating from the end of the string. Count the characters until we find a space, which indicates the end of the last word.
- Chinese: 从字符串末尾开始迭代，计算字符直到遇到空格，这标志着最后一个单词的结束。
Return the Length of the Last Word / 返回最后一个单词的长度
```
return length
```
- English: Return the count of characters, which gives the length of the last word.
- Chinese: 返回字符的计数，得到最后一个单词的长度。

Recursive Solution

Approach: Recursive Backtracking / 递归回溯

We can recursively find the length of the last word by starting from the end of the string and counting characters until the first space is encountered, or until the start of the string is reached.

Recursive Algorithm / 递归算法

Remove trailing spaces using the strip() method.
Recursively count the length of the last word from the end of the string.
Base case: If the first space is encountered or the start of the string is reached, return the count of characters.

Recursive Implementation / 递归实现

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.strip()  # Trim trailing spaces

        def countLastWord(i, length):
            if i < 0 or s[i] == ' ':  # Base case: if space is found or beginning of the string
                return length
            return countLastWord(i - 1, length + 1)  # Recursively count characters

        return countLastWord(len(s) - 1, 0)

Recursive Solution Explanation / 递归解决方案解释

Trim Trailing Spaces / 修剪尾部空格
```
s = s.strip()
```
- English: Remove any trailing spaces from the string to ensure we start from the last word.
- Chinese: 删除字符串末尾的空格，确保我们从最后一个单词开始处理。
Recursive Call to Count Characters / 递归调用以计算字符数
```
def countLastWord(i, length):
   if i < 0 or s[i] == ' ':
       return length
   return countLastWord(i - 1, length + 1)
```
- English: Recursively count the characters of the last word by moving backward through the string. If a space is found or we reach the start of the string, return the count.
- Chinese: 通过递归向后遍历字符串，计算最后一个单词的字符数。如果遇到空格或到达字符串的开头，返回计数。
Return the Result / 返回结果
```
return countLastWord(len(s) - 1, 0)
```
- English: Start the recursive counting process from the last character in the string and return the length of the last word.
- Chinese: 从字符串中的最后一个字符开始递归计数，返回最后一个单词的长度。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the length of the string. We iterate through the string once to find the last word.
Space Complexity / 空间复杂度:
- Iterative Solution: O(1), since no extra space is used.
- Recursive Solution: O(n), due to the recursion stack.

Key Concept / 关键概念

String Traversal / 字符串遍历: By iterating from the end of the string, we can efficiently find the last word by counting characters until we hit a space.
Recursion / 递归: In the recursive solution, we backtrack through the string from the last character to the first, counting characters until the last word is fully processed.

Summary / 总结

English: We can solve the problem of finding the length of the last word by traversing the string from the end. Both iterative and recursive approaches achieve the same result, with recursion breaking the problem down step by step.
Chinese: 我们可以通过从字符串末尾遍历来解决寻找最后一个单词长度的问题。迭代和递归方法都能达到相同的结果，递归方法通过逐步分解问题来实现。

Tips / 提示

English: Ensure to trim trailing spaces before starting the counting process to avoid counting spaces as part of the last word.
Chinese: 确保在开始计数过程之前修剪末尾的空格，以避免将空格计入最后一个单词的一部分。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice string manipulation problems to improve your understanding of string traversal and handling corner cases with spaces.
Chinese: 练

习字符串操作问题，以提高对字符串遍历和处理空格边缘情况的理解。

Length of Last Word - Leetcode 58 - Python by NeetCode

Post Views: 38

CODEBITWAVE