Leetcode – Length of Last Word Solution in Python

Spread the love

In today’s article, we’re going to delve into one of the common string manipulation problems on LeetCode: The Length of Last Word problem. This problem is particularly interesting because it presents an opportunity to refine our knowledge and skills on string handling, understanding of built-in functions, edge cases handling, as well as algorithmic time and space complexity.

Problem Statement

First things first, let’s clarify the problem statement:

Length of Last Word (LeetCode problem 58)

Given a string s consisting of some words separated by some number of 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

Constraints

1 <= s.length <= 10^4

s consists of only English letters and spaces ‘ ‘.

s does not contain any leading or trailing spaces.

There is at least one word in s.

Initial Thoughts

In this problem, we’re asked to determine the length of the ‘last’ word in a given string. The naive approach would be to split the string into words and then return the length of the last word. However, this approach is not optimal and doesn’t address edge cases properly. So, it’s crucial to keep these nuances in mind when solving this problem.

Approach 1: Using Python’s Built-in Functions

Python’s built-in functions simplify the process of solving this problem considerably. We will start by using the strip() function to remove leading and trailing white spaces. Next, we will split the string into words using the split() function, which separates the string at white spaces by default.

Let’s implement this in Python:

def lengthOfLastWord(s: str) -> int:
    s = s.strip()  # Remove leading and trailing spaces
    words = s.split()  # Split the string into words
    return len(words[-1])  # Return the length of the last word

While this code works fine and passes all test cases, it might not be the most optimal solution as the split function will process the entire string even if it’s not necessary.

Approach 2: Starting from the End

Another approach would be to start from the end of the string and move backwards, essentially looking for the ‘last’ word first. This approach is more efficient because we don’t have to process the entire string, especially when the string is very large.

Here is the Python code implementing this approach:

def lengthOfLastWord(s: str) -> int:
    length = 0
    s = s.rstrip()  # Remove trailing spaces

    for i in range(len(s)-1, -1, -1):  # Start from the end of the string
        if s[i] == ' ':  # If we encounter a space, we've found the end of the last word
            break
        length += 1  # If it's not a space, increment the word length counter

    return length

This approach works by initializing a counter, length, to 0. Then, we strip any trailing spaces from the string. We then iterate over the string in reverse order. If we encounter a space, we break out of the loop because we’ve found the end of the last word. If the character is not a space, we increment our counter. Finally, we return the counter, which holds the length of the last word.

Time and Space Complexity

Both of the above approaches have a time complexity of O(n), where n is the length of the string. This is because in the worst-case scenario, we need to iterate over every character in the string.

For the space complexity, the first approach has a space complexity of O(m), where m is the number of words in the string. This is due to the usage of the split() function, which creates a new list containing all the words in the string.

The second approach, on the other hand, has a constant space complexity, O(1), because we only use a counter to keep track of the length of the last word, regardless of the size of the input string.

Conclusion

In conclusion, we’ve examined two distinct approaches to solving the Length of Last Word problem on LeetCode using Python. The first approach was straightforward and used built-in Python functions. The second approach was more efficient, particularly in terms of space complexity, as it iterated from the end of the string to find the last word.

This problem is a classic example of how understanding the nature of the problem and the properties of the programming language being used can lead to more efficient solutions. So, always consider these aspects when tackling similar problems.

Leave a Reply