Kim's Blog

「58. 最后一个单词的长度」题解

4/20/2021 LeetCodeAlgorithm

# 58. 最后一个单词的长度 (opens new window)

# 题目描述

给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0 。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5

示例 2：

输入：s = " "
输出：0

提示： 1 <= s.length <= 104 s 仅有英文字母和空格 ' ' 组成

相关信息：

  • 难度：简单
  • 标签：字符串

# 题解

本题是名副其实的简单题，作为老 API 调用怪，我直接几个 API 一把梭就搞定了，很快啊～嘿嘿，好了，不皮了。本题主要需要处理的情况有三种：

  1. "Hello Word"：这是比较正常的情况，最后的位置存在单词。
  2. "Hello Word "：这种情况就是以空格结尾，但是空格之前有单词存在，所以 Word 应该是它的最后一个单词，这一点在题目的描述中表述得不是很清楚。
  3. " "：这种情况就是纯的空字符串，直接返回零 0⃣️。

# 方法一：双指针

首先，我们从最原始的写法开始吧，然后一步步用 API 替代。

第一种实现思路，尾部指针从尾部开始，忽略尾部空格，指向尾部第一个非空格字符，然后头部指针从尾部出发，一直移动，直到遇见第一个空字符。返回尾部指针和头部指针之间的差值，即为单词长度。

/**
执行用时: 84 ms
内存消耗: 37.6 MB
 */
var lengthOfLastWord = function (s) {
  let end = s.length - 1; //尾部指针
  while (end >= 0 && s[end] == " ") end--; //忽略尾部空格
  if (end < 0) return 0;
  let start = end; //头部指针出发
  while (start >= 0 && s[start] != " ") start--;
  return end - start;
};

上边这种实现方式不太好的是使用了两次循环，不过一般尾部空格不会太多，所以实际影响也还好。

第二种实现方式就是将两次循环压缩到了一次循环，直接从尾部向头部循环一次，从第一个非空格字符开始计数，一旦再次遇到空格便结束循环。

/**
执行用时: 72 ms
内存消耗: 37.6 MB
*/
var lengthOfLastWord = function (s) {
  let count = 0;
  for (let i = s.length - 1; i > -1; i--) {
    if (s[i] === " ") {
      if (count == 0) continue; //count为零时便一直跳过末尾的空字符
      break; //count非零之后，第二次遇到空字符就结束
    }
    count++;
  }
  return count;
};

从结果可以看出，这种实现方法确实有所提升。

另外，有同学会在函数体首部单独判断 s===' '，然后直接返回 0；我个人认为没有这个必要，因为所有遍历都是从尾部开始的，空字符串相比其他状况已经缩减了许多步骤，相比于直接返回 0，并没有多处太多处理时间。经过我实际测试，弃掉这个判断，函数运行速度反而提升了，非常玄学。总之后，并非所有特殊情况，在函数体首部单独判断处理之后都能提升大幅度提升运行速率，应视具体情况而定。

# 方法二：开启 API 大赏

# filter+split

/**
执行用时: 64 ms
内存消耗: 37.7 MB
 */
var lengthOfLastWord = function (s) {
  //分割后空数组全部筛去
  let words = s.split(" ").filter((item) => item != "");
  //注意如果原数组全部为空格，筛选后words为空数组
  return words.length != 0 ? words[words.length - 1].length : 0;
};

# trim+split+reserve

/*
执行用时: 76 ms
内存消耗: 38.1 MB
*/
//这样反转数组还是比较耗时耗空间的
var lengthOfLastWord = function (s) {
  return s.trim().split(" ").reverse()[0].length;
  //trim 去除首尾空格；split 按空格分割，reverse 反转数组。
};

# trim + split+pop

/*
执行用时: 108 ms
内存消耗: 37.7 MB
*/
//果然开启API之后，运行速度会降很多，但我认为这是我目前想到的最简单的写法
var lengthOfLastWord = function (s) {
  return s.trim().split(" ").pop().length;
  //trim 去除首尾空格；split 按空格分割，pop弹出尾部单词
};

以上就是本题的所有题解啦，感谢你能看到这里，如果本文对你有所帮助的话，别忘了给一个 Star 嗷～ 如果你对题解中的代码有不一样的优化意见，也欢迎你在 issue 中指出～ 最重要的是不要忘了点点关注嗷（Github (opens new window)、力扣 (opens new window)），以便获取我最新的题解以及文章通知。

# 参考文章：

# 全部代码

/*
 * @lc app=leetcode.cn id=58 lang=javascript
 *
 * [58] 最后一个单词的长度
 *
 * https://leetcode-cn.com/problems/length-of-last-word/description/
 *
 * algorithms
 * Easy (35.14%)
 * Likes:    343
 * Dislikes: 0
 * Total Accepted:    211.4K
 * Total Submissions: 601.6K
 * Testcase Example:  '"Hello World"'
 *P
 * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
 * 
 * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "Hello World"
 * 输出：5
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "   fly me   to   the moon  "
 * 输出：4
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：s = "luffy is still joyboy"
 * 输出：6
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= s.length <= 10^4
 * s 仅有英文字母和空格 ' ' 组成
 * s 中至少存在一个单词
 * 
 * 
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
 var lengthOfLastWord = function(s) {
    let end = s.length - 1;//尾部指针
    while(end >= 0 && s[end] == ' ') end--;//忽略尾部空格
    if(end < 0) return 0;
    let start = end;//头部指针出发
    while(start >= 0 && s[start] != ' ') start--;
    return end - start;
};
// @lc code=end

var lengthOfLastWord = function(s) {
    let count=0;
    for(let i=s.length-1;i>-1;i--){
        if(s[i]===' '){
            if(count==0)continue;//count为零时便一直跳过末尾的空字符
            break//count非零之后，第二次遇到空字符就结束
        }
        count++
    }
    return count;
};
var lengthOfLastWord = function(s) {
    //分割后空数组全部筛去
    let words = s.split(' ').filter((item)=>item != '')
    //注意如果原数组全部为空格，筛选后words为空数组
    return words.length != 0?words[words.length-1].length:0
};

//这样反转数组还是比较耗时耗空间的
var lengthOfLastWord = function(s) {
    return s.trim().split(' ').reverse()[0].length
    //trim 去除首尾空格；split 按空格分割，reverse 反转数组。
};

//果然开启API之后，运行速度会降很多，但我认为这是我目前想到的最简单的写法
var lengthOfLastWord = function(s) {
    return s.trim().split(" ").pop().length;
  //trim 去除首尾空格；split 按空格分割，pop弹出尾部单词
};

「66. 加一」题解