Leetcode No.58 Length of Last Word最后一个单词的长度(c++实现）

1. 题目

1.1 英文题目

Given a string s consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0.

A word is a maximal substring consisting of non-space characters only.

1.2 中文题目

给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0 。

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

1.3输入输出

输入	输出
s = "hello qq"	2
s = " hello "	1
s = "a"	1
s = " "	0

1.4 约束条件

• 1 <= s.length <= 104
• s consists of only English letters and spaces ' '.

2. 分析

2.1 一般算法

进行逆序遍历

class Solution {
public:
    int lengthOfLastWord(string s) {
        int sLen = s.size();
        int start = 0;//最后一个单词的最后一个字母位置
        int end = 0;//最后一个单词前的空格位置(注意：不是最后一个单词的第一个字母位置）
        for (int i = sLen - 1; i >= 0; i--)//逆序遍历
        {
            if (start == 0 && s[i] != ' ')//第一个非空格处，记为start
                start = i;
            else if (start != 0 && s[i] == ' ')//已经有start（也就是找到最后一个单词）的前提下，找到第二个空格，记为end，且退出循环
            {
                end = i;
                break;
            }
            if (i == 0 && s[i] != ' ')//若一直遍历到0处才找到非空格元素，则将end-1
                end--;
        }
        return start - end;
    }
};

2.2 简化算法

代码如下：

class Solution {
public:
    int lengthOfLastWord(string s) { 
        int len = 0, tail = s.length() - 1;
        while (tail >= 0 && s[tail] == ' ') tail--;//逆序寻找第一个非空格位置
        while (tail >= 0 && s[tail] != ' ') {
            len++;
            tail--;
        }//逆序寻找第二个非空格位置
        return len;
    }
};

代码参考：https://leetcode.com/problems/length-of-last-word/discuss/21892/7-lines-4ms-C%2B%2B-Solution