【数据结构与算法】之深入解析“最后一个单词的长度”的求解思路与算法示例

一、题目要求

• 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开，返回字符串中最后一个单词的长度。
• 单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
• 示例 1：

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

  

 

  
1
  
2
 

• 示例 2：

输入：s = "   fly me   to   the moon  "
输出：4

  

 

  
1
  
2
 

• 示例 3：

输入：s = "luffy is still joyboy"
输出：6

  

 

  
1
  
2
 

• 提示：
• • 1 <= s.length <= 104；
• • s 仅有英文字母和空格 ’ ’ 组成；
• • s 中至少存在一个单词。

二、求解算法

① 反向遍历

• 题目要求得到字符串中最后一个单词的长度，可以反向遍历字符串，寻找最后一个单词并计算其长度。
• 由于字符串中至少存在一个单词，因此字符串中一定有字母。首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。
• 从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。
• Java 示例：

class Solution {
    public int lengthOfLastWord(String s) {
        int index = s.length() - 1;
        while (s.charAt(index) == ' ') {
            index--;
        }
        int wordLength = 0;
        while (index >= 0 && s.charAt(index) != ' ') {
            wordLength++;
            index--;
        }
        return wordLength;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

• C++ 示例：

class Solution {
public:
    int lengthOfLastWord(string s) {
        int index = s.size() - 1;

        while (s[index] == ' ') {
            index--;
        }
        int wordLength = 0;
        while (index >= 0 && s[index] != ' ') {
            wordLength++;
            index--;
        }

        return wordLength;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

② 字符串遍历

• 从字符串末尾开始向前遍历，其中主要有两种情况：
• • 第一种情况，以字符串"Hello World"为例，从后向前遍历直到遍历到头或者遇到空格为止，即为最后一个单词"World"的长度 5；
• • 第二种情况，以字符串"Hello World “为例，需要先将末尾的空格过滤掉，再进行第一种情况的操作，即认为最后一个单词为"World”，长度为 5。
• 所以完整过程为先从后过滤掉空格找到单词尾部，再从尾部向前遍历，找到单词头部，最后两者相减，即为单词的长度
• 时间复杂度：O(n)，n 为结尾空格和结尾单词总体长度。
• Java 示例：

class Solution {
    public int lengthOfLastWord(String s) {
        int end = s.length() - 1;
        while(end >= 0 && s.charAt(end) == ' ') end--;
        if(end < 0) return 0;
        int start = end;
        while(start >= 0 && s.charAt(start) != ' ') start--;
        return end - start;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/Forever_wj/article/details/122824382