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

题目:给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 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 协议》,转载必须注明作者和本文链接

阿德

zhangdeTalk
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!