LeetCode 58 · Matrix & strings

Length of Last Word, explained with a picture

Walking back from the end of a sentence.

Matrix & strings
▶ Watch it step by step

The problem

Return the length of the last word in a sentence (words are separated by spaces; there may be trailing spaces).

Input:  "fly me to the moon  "
Output: 4

Picture it

Picture walking backwards from the end of the sentence. Skip any trailing spaces, then count letters until you hit the next space or the start.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Scan from the end. O(n).

Python solution

def length_of_last_word(s):
    i = len(s) - 1
    while i >= 0 and s[i] == " ":
        i -= 1                      # skip trailing spaces
    length = 0
    while i >= 0 and s[i] != " ":
        length += 1
        i -= 1
    return length

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.