LeetCode 58. 最后一个单词的长度（易）

先去掉字符串最后的空格，然后从最后一位向前加，直到遇到第一个空格。

题目

给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

示例

示例一

1
2
输入: "Hello World"
输出: 5

示例二

1
2
输入: "b   a    "
输出: 1

考察知识点

字符串

核心思想

方法一

先按照 " " 将字符分段，然后遍历返回第一个不是空格的子串的长度。

方法二

  • 先去掉字符串最后的空格
  • 按照 " " 将字符分段
  • 返回最后一个子串的长度即可

方法三

  • 先去掉字符串最后的空格
  • 然后从最后一位向前加，直到遇到第一个空格。

Python版本

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        _segment = s.split(" ")
        length = len(_segment)
        for i in range(length - 1, -1, -1):
            if _segment[i] != "":
                return len(_segment[i])
        return 0

print("leet code accept!!!")
Input = ["hello world", "b   a    "]
Input1 = []
Answer = [5, 1]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.lengthOfLastWord(Input[i])
        print(reslut == Answer[i])

时间复杂度为 \(O(n)\)，可能输入的字符串就是一个长度为n的空串，这样就会遍历n次才得到结果。
执行用时 :44 ms, 在所有 Python3 提交中击败了22.65%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了16.03%的用户

方法二

1
2
3
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.rstrip().split(" ")[-1])

执行用时 :40 ms, 在所有 Python3 提交中击败了33.05%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了16.03%的用户

方法二改进版 未调用任何Python内建函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        def remove_str(_str, target=" "):  # 去除结尾处字符串
            is_end = False
            length_n = 0 - len(target)
            while not is_end:
                if _str[length_n:] == target:
                    _str = _str[:length_n]
                else:
                    is_end = True
            return _str
        
        def split_str(_str, target=" "):  # 将字符串分段
            res = []
            while True:
                index = index_str(_str)
                if index == -1:
                    res.append(_str)
                    break
                res.append(_str[:index])
                _str = _str[index+1:]
            return res
        
        def index_str(_str, target=" "):  # 获取字符串中特特定字符的起始位置
            length_target = len(target)
            for i in range(len(_str)):
                if _str[i:length_target+i] == target:
                    return i
            return -1

        s = remove_str(s)  # 去除末尾空格
        _segment = split_str(s)  # 将字符串分段
        return len(_segment[-1])  # 返回最后一个子串的长度

执行用时 :40 ms, 在所有 Python3 提交中击败了33.05%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了16.03%的用户

方法三的实现 未调用任何Python内建函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        def remove_str(_str, target=" "):
            is_end = False
            length_n = 0 - len(target)
            while not is_end:
                if _str[length_n:] == target:
                    _str = _str[:length_n]
                else:
                    is_end = True
            return _str

        s = remove_str(s)
        count = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] != " ":
                count += 1
            else:
                break
        
        return count

执行用时 :40 ms, 在所有 Python3 提交中击败了33.05%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了16.03%的用户

有效语法糖

1、Python的 rstrip 方法：删除 string 字符串末尾的指定字符（默认为空格）。

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/python

str = "     this is string example....wow!!!     ";
print str.rstrip();
str = "88888888this is string example....wow!!!8888888";
print str.rstrip('8');

# 输出
     this is string example....wow!!!
88888888this is string example....wow!!!