每日一道算法:最后一个单词的长度
题目:给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 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):https://leetcode-cn.com/problems/length-of...
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: