每日一道算法：最后一个单词的长度

题目：给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s，返回其最后一个单词的长度。

如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

示例1：

输入：”Hello World”

输出：5

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

解法一：字符串遍历

相关标签

* 字符串

思路分析：

从字符串尾部进行反序遍历，主要有三种情况：

第一种：最后一个单词的后边都是空格，比如"Hello world "，此时需要把尾部的空格都过滤掉，进行第二种情况的操作

第二种：当最后一个单词后边没有空格时，比如"Hello world"，此时把$end赋值给$start，一直遍历到，直到出现空格或者到字符串最开始，此时结果就是：$end - $start

第三种：如果全部都是空格时，即$end < 0，返回0

PHP代码实现：

/**
 * @param String $s
 * @return Integer
 */
function lengthOfLastWord($s) {
    $end = strlen($s) -1;
    while($end>=0 && $s[$end] == ' '){//过滤掉最右边的空格
        $end--;
    }
    if($end < 0){//当全部都是空格时
        return 0;
    }
    $start = $end;//此时最后的一位字符肯定是最后一个单词的最后一位
    while($start >= 0 && $s[$start] != ' '){//寻找最后一个单词的开头字符的位置
        $start--;
    }
    return $end - $start;
}

使用：
$s = "Hello world";
var_dump(lengthOfLastWord($s));

复杂度分析：

时间复杂度： O(n)
n是结尾为空格和最后一个单词的总长度
空间复杂度： O(n)
n是最后一个单词的长度

解题关键

做算法题，一定要善于总结和找出规律，考虑要全面，各种可能的情况都要想到。

github

以后每次题解都会上传到这个项目

LeetCode_PHP：https://github.com/zhangdejian/LeetCode_PHP

题目来源

力扣（LeetCode）：https://leetcode-cn.com/problems/length-of...

本作品采用《CC 协议》，转载必须注明作者和本文链接