字符串题目:最后一个单词的长度

wuchangjian2021-11-15 18:02:45编程学习

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:最后一个单词的长度

出处:58. 最后一个单词的长度

难度

3 级

题目描述

要求

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

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

示例

示例 1:

输入: s   =   "Hello   World" \texttt{s = "Hello World"} s = "Hello World"
输出: 5 \texttt{5} 5
解释:最后一个单词是 World \texttt{World} World,长度为 5 \texttt{5} 5

示例 2:

输入: s   =   "   fly   me   to   the   moon   " \texttt{s = " fly me to the moon "} s = " fly me to the moon "
输出: 4 \texttt{4} 4
解释:最后一个单词是 moon \texttt{moon} moon,长度为 4 \texttt{4} 4

示例 3:

输入: s   =   "luffy   is   still   joyboy" \texttt{s = "luffy is still joyboy"} s = "luffy is still joyboy"
输出: 6 \texttt{6} 6
解释:最后一个单词是 joyboy \texttt{joyboy} joyboy,长度为 6 \texttt{6} 6

数据范围

  • 1 ≤ s.length ≤ 10 4 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{4} 1s.length104
  • s \texttt{s} s 仅由英语字母和空格 ‘   ’ \texttt{` '} ‘ ’ 组成
  • s \texttt{s} s 中至少存在一个单词

解法

思路和算法

要得到字符串中最后一个单词的长度,需要首先得到字符串中最后一个单词的开始下标和结束下标。

如果字符串中存在非空格字符,则字符串中最后一个非空格字符即为最后一个单词的结束字符,对应的下标即为最后一个单词的结束下标。因此,从字符串的末尾反向遍历字符串,遇到空格则跳过,第一次遇到非空格字符时,将其下标记为最后一个单词的结束下标。

得到最后一个单词的结束下标之后,从该下标开始,继续反向遍历字符串,遇到非空格字符则跳过,第一次遇到空格或者下标小于 0 0 0 时,遍历到的下标位置加 1 1 1 即为最后一个单词的开始下标。

最后一个单词的长度即为最后一个单词的结束下标与开始下标之差加 1 1 1

由于字符串中存在至少一个单词,因此字符串中一定存在非空格字符,上述做法可以得到最后一个单词的长度。

代码

class Solution {
    public int lengthOfLastWord(String s) {
        int length = s.length();
        int wordStart = -1, wordEnd = -1;
        int index = length - 1;
        while (index >= 0) {
            if (s.charAt(index) == ' ') {
                index--;
            } else {
                wordEnd = index;
                break;
            }
        }
        while (index >= 0) {
            if (s.charAt(index) != ' ') {
                index--;
            } else {
                wordStart = index + 1;
                break;
            }
        }
        if (index < 0) {
            wordStart = 0;
        }
        return wordEnd - wordStart + 1;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是字符串 s s s 的长度。需要反向遍历字符串 s s s 一次。

  • 空间复杂度: O ( 1 ) O(1) O(1)

相关文章

samba服务的配置与使用

samba服务的配置与使用

实验目的 希望在自己的windows 物理主机上面可以直接访问 linux 服务器&#x...

电池包IPX9K、IPX9测试目的

电池包IPX9K、IPX9测试目的

IPX9K、IPX9测试前提条件:   经过高低温、振动等测试之后的...

C语言之快速幂优化水仙花数

#include <stdio.h> int quickpow(int x,...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。