LeetCode 面试经典 150_数组/字符串_最后一个单词的长度（19_58_C++_简单）(反向遍历)

题目描述：

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

输入输出样例：

示例 1：
输入：s = “Hello World”
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：
输入：s = " fly me to the moon "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：
输入：s = “luffy is still joyboy”
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

提示：
1 <= s.length <= 10⁴
s 仅有英文字母和空格 ’ ’ 组成
s 中至少存在一个单词

题解：

解题思路：

思路一（反向遍历）：

1、可以从后向前遍历字符串，当碰到第一个字母时开始计数，当碰到空格时停止计数。

2、复杂度分析：
① 时间复杂度：O(n)，n 代表字符串中字符的个数，最坏的情况需要遍历整个字符串。
② 空间复杂度：O(1)。

代码实现

代码实现（思路一（反向遍历））：

class Solution1 {
public:// 计算字符串 s 中最后一个单词的长度int lengthOfLastWord(string s) {// 从字符串的最后一个字符开始int i = s.size() - 1;// 向前跳过字符串末尾的空格或非字母字符while (!isalpha(s[i])) {i--;}// 记录最后一个单词的长度int ans = 0;// 继续向前遍历，直到遇到非字母字符或遍历完字符串while (i >= 0 && isalpha(s[i])) {ans++;  // 每遇到一个字母，长度加 1i--;     // 向前移动}// 返回最后一个单词的长度return ans;}
};

代码实现（对思路一代码进行优化）：

/** 因除字母外的字符只包含字空格，所以我们可以判断当前字符是否为空格来计算出字符串中 最后一个 单词的长度。* 判断字母最多需要四个判断(c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); 而空格的判断只需要一个 * */class Solution2 {
public:// 计算字符串 s 中最后一个单词的长度int lengthOfLastWord(string s) {// 从字符串的最后一个字符开始int i = s.size() - 1;// 向前跳过字符串末尾的空格// 如果遇到空格，继续向前跳过直到遇到非空格字符while (i >= 0 && s[i] == ' ') {i--;}// 记录最后一个单词的长度int ans = 0;// 继续向前遍历，直到遇到空格或遍历完字符串// 这里判断非空格字符，来识别最后一个单词while (i >= 0 && s[i] != ' ') {ans++;  // 每遇到一个字符，单词长度加 1i--;     // 向前移动}// 返回最后一个单词的长度return ans;}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution1 {
public:// 计算字符串 s 中最后一个单词的长度int lengthOfLastWord(string s) {// 从字符串的最后一个字符开始int i = s.size() - 1;// 向前跳过字符串末尾的空格或非字母字符while (!isalpha(s[i])) {i--;}// 记录最后一个单词的长度int ans = 0;// 继续向前遍历，直到遇到非字母字符或遍历完字符串while (i >= 0 && isalpha(s[i])) {ans++;  // 每遇到一个字母，长度加 1i--;     // 向前移动}// 返回最后一个单词的长度return ans;}
};int main(int argc, char const *argv[])
{string str="luffy is still joyboy";Solution1 s;cout<<s.lengthOfLastWord(str);return 0;
}

LeetCode 面试经典 150_数组/字符串_最后一个单词的长度（19_58)原题链接
欢迎大家和我沟通交流(✿◠‿◠)