Leetcode Study Day 10

2023-09-28

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 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.

My solution

At first, my solution is to split the string by space and store the words in a vector. Then I return the length of the last word in the vector. So I learned about how to split by space in C++:

vector <string> tokens;
istringstream iss(s);
string token;
while(iss >> token)
    tokens.push_back(token);
return (tokens[tokens.size()-1].length());

In this code,

1	std::istringstream iss(s);

std::istringstream is a type provided by the <sstream> header. It stands for “input string stream” and can be thought of as a stream that operates on strings, just as you’d read from or write to files with file streams.
When you create an istringstream with a string argument, the content of the string is loaded into the stream. In this case, the content of s is loaded into the iss stream, and you can then “read” from this stream using extraction (>>) operators, as you would with std::cin or any other stream.

1	std::string token;

This line simply declares a string named token. This will be used to hold individual space-separated segments (tokens) from the original string as we extract them from the stream.

1
2
3

while (iss >> token) {
    tokens.push_back(token);
}

The loop’s condition, iss >> token, tries to extract a “word” (a space-separated segment) from the iss stream and put it into the token string. If the extraction is successful (meaning there’s still content in the stream), the loop continues. If the extraction fails (meaning there’s no more content to extract), the loop exits.
The >> operator, when used with streams and strings, automatically splits on whitespace (like spaces, newlines, and tabs), so each iteration extracts one word from the string up to the next space or end of the string.
tokens.push_back(token); adds the extracted token to the tokens vector.

The loop, in essence, continues extracting words from iss and adding them to the tokens vector until there’s no more content left in iss.

A solution with more algorithmic idea

Then I thought that a string is actually a vector in c++, and we can use a more algorithmic idea to solve it. To be specific, we can iterate the string from the last to the first, if we meet a character that is not a space, we increase the count by one, if we meet a space and it is behind all the characters, we skip it, if we meet a space and the count is not 0, we then break our loop and return the count:

class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.size();
        int count = 0;
        for (int i = n -1; i >= 0; i--){
            if (s[i] == ' ' && count == 0)
                continue;
            if (s[i] != ' ')
                count ++;
            else if (s[i] == ' ')
                break;
        }
        return count;
    }
};