58. Length of Last Word
Description
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 1:
Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5.
Example 2:
Input: s = " fly me to the moon " Output: 4 Explanation: The last word is "moon" with length 4.
Example 3:
Input: s = "luffy is still joyboy" Output: 6 Explanation: The last word is "joyboy" with length 6.
Constraints:
1 <= s.length <= 104
s
consists of only English letters and spaces' '
.- There will be at least one word in
s
.
Solutions
Solution 1: Reverse Traversal + Two Pointers
We start traversing from the end of the string $s$, find the first character that is not a space, which is the last character of the last word, and mark the index as $i$. Then continue to traverse forward, find the first character that is a space, which is the character before the first character of the last word, and mark it as $j$. Then the length of the last word is $i - j$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|