面试经典算法150题系列-最后一个单词的长度

最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

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

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

实现思路1：将字符串转成全为单词的字符串列表，然后直接返回最后一个单词的长度即可。

处理：将所给字符串，利用正则表达式进行匹配筛选，将空格去掉后 得到一个全为单词的字符串数组，然后返回最后一个单词的长度即可。

实现代码：

    public  int lengthOfLastWord(String s) {
        //正则表达式匹配去掉空格，得到单词数组
        String[] words = s.split("\\s+");
        //判断数组是否为空
        if (words.length == 0) {
            return 0;
        }
        //返回最后一个单词的长度
        return words[words.length - 1].length();
        //等价于  最后一个单词在数组的索引  int lastWordIndex=words.length-1;
        //       最后一个单词的长度  int lastWordLength=words[lastWordIndex].length();
    }

• split: 这是Java String 类的一个方法，用于根据指定的分隔符将字符串分割成多个子字符串，并返回一个子字符串数组。
• \\s+: 这是一个正则表达式，其中 \\s 匹配任何空白字符（包括空格、制表符、换行符等），而 + 表示匹配一个或多个前面的字符。因此，\\s+ 将匹配一个或多个连续的空白字符。

（正则表达式详解，在文章的后面进行补充，如果有不懂的可以看看后面的知识补充部分）

实现思路2：通过从后往前遍历，直接计算最后一个单词的长度。

实现步骤：

1.我们需要定义一个变量用于记录最后一个单词的起始索引。

2.去掉字符串前后的字符串（确保前后没有空格），然后从后往前开始遍历，记录当前索引，若是没有遇到空格，则更新用于记录的索引，遇到空格时，遍历使用break关键字跳出循环，说明最后一个单词已经遍历完。

3.返回最后一个单词的长度：字符串长度-起始索引

实现代码：

 public int lengthOfLastWord(String s) {
    // 如果字符串s为空或为null，返回0
    if(s.length() == 0 || s == null) {
        return 0;
    }
    // 去除字符串s两端的空白字符
    s = s.trim();
    
    // 初始化start变量，这将用于记录最后一个单词的起始索引
    int start = 0;
    
    // 从字符串的末尾开始向前遍历，直到遇到一个非空格字符
    for(int i = s.length() - 1; i >= 0; i--) {
        if(s.charAt(i) == ' ') {
            // 遇到空格，结束循环
            break;
        }
        // 更新start为当前非空格字符的索引
        start = i;
    }
    
    // 计算最后一个单词的长度，即字符串长度减去start
    // 由于start是在最后一个单词的第一个字符上，所以用字符串长度减去start
    // 得到最后一个单词的长度
    return s.length() - start;
}

charAt() 是 String 类的一个方法，用于返回指定索引处的字符。

第二种思路实现简单，执行效率比第一种要高。

知识补充：

正则表达式

正则表达式（Regular Expression，简称Regex）是一种用于匹配字符串中字符组合的模式（Pattern）。它使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在编程语言和文本编辑器中，正则表达式通常用于搜索、替换、字符串分割等操作。

以下是一些基本的正则表达式元素和它们的含义：

• .：匹配任意单个字符（除了换行符）。
• ^：匹配输入字符串的开始位置。
• $：匹配输入字符串的结束位置。
• *：匹配前面的子表达式零次或多次。
• +：匹配前面的子表达式一次或多次。
• ?：匹配前面的子表达式零次或一次。
• {n}：恰好匹配确定的 n 次数。
• {n,}：至少匹配 n 次。
• {n,m}：最少匹配 n 次且最多 m 次。
• []：匹配方括号内的任意字符（字符集）。
• |：逻辑或操作符，匹配选项或多个表达式中的一个。
• \：转义特殊字符或表示特殊序列。
• ()：将多个表达式组合成一个子表达式，用于分组。

特殊序列的例子：

• \d：匹配任意数字，等同于 [0-9]。
• \w：匹配任意字母数字字符，包括下划线，等同于 [A-Za-z0-9_]。
• \s：匹配任意的空白符（包括空格、制表符、换行符等）。

正则表达式在不同的编程语言和工具中语法可能略有不同，但大多数基本元素是通用的。例如，在Java中，你可以使用 java.util.regex 包中的类来处理正则表达式。在Python中，你可以使用 re 模块。

下面是一些正则表达式的使用示例：

• 匹配一个电子邮件地址：[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+
• 匹配一个URL：https?://[^\s/$.?#].[^\s]*
• 匹配一个电话号码：(\+?\d{1,3})?[-. ]?\d{1,4}[-. ]?\d{1,4}[-. ]?\d{1,9}
• 匹配一个日期格式（如：YYYY-MM-DD）：\d{4}-\d{2}-\d{2}

正则表达式是文本处理的强大工具，但它们也可能相当复杂，特别是当涉及到复杂的模式匹配时。