截断句子

难度: Easy

句子是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。每个单词仅由大小写英文字母组成（不含标点符号）。

例如，"Hello World"、"HELLO" 和 "hello world hello world" 都是句子。

给你一个句子 s 和一个整数 k ，请你将 s 截断，使截断后的句子仅含前 k 个单词。返回截断 s 后得到的句子。

示例 1：

输入：s = "Hello how are you Contestant", k = 4
输出："Hello how are you"
解释：
s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
前 4 个单词为 ["Hello", "how", "are", "you"]
因此，应当返回 "Hello how are you"

示例 2：

输入：s = "What is the solution to this problem", k = 4
输出："What is the solution"
解释：
s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]
前 4 个单词为 ["What", "is", "the", "solution"]
因此，应当返回 "What is the solution"

示例 3：

输入：s = "chopper is not a tanuki", k = 5
输出："chopper is not a tanuki"

提示：

1 <= s.length <= 500
k 的取值范围是 [1, s 中单词的数目]
s 仅由大小写英文字母和空格组成
s 中的单词之间由单个空格隔开
不存在前导或尾随空格

Submission

运行时间: 20 ms

内存: 15.7 MB

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        idx=None
        for i,c in enumerate(s):
            if c==' ':
                k-=1
            if not k:
                idx=i
                break
        if idx!=None:
            return s[:idx]
        else:
            return s

Explain

题解的核心思路是通过遍历句子中的每个字符，并在遇到空格时减少计数器 k，因为空格代表一个单词的结束。当 k 减到 0 时，我们知道已经遍历完 k 个单词，所以此时的字符索引即是我们需要截断句子的位置。如果遍历完整个句子后 k 还没有减到 0，说明句子中的单词数不超过 k，因此直接返回整个句子。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        idx = None # 初始化索引为 None，用于记录截断位置
        for i, c in enumerate(s): # 遍历句子中的每个字符及其索引
            if c == ' ': # 如果字符是空格，表示一个单词的结束
                k -= 1 # 减少单词计数
            if not k: # 如果单词计数减到 0，表示已找到截断位置
                idx = i # 记录截断位置的索引
                break # 跳出循环
        if idx != None: # 如果找到了截断位置
            return s[:idx] # 返回截断后的句子
        else: # 如果没有找到截断位置，表示句子单词数不足 k 个
            return s # 直接返回整个句子

Explore

算法在遇到每个空格时减少计数器 k 的值，连续空格会被视为多个单词的结束。这意味着如果句子中有连续空格，算法会错误地将这些空格计算为多个单词的分隔，从而导致提前截断句子。因此，这种算法不能正确处理含有连续空格的情况，除非加入逻辑来忽略连续的空格。

如果句子最后一个单词后存在额外空格，这个算法会将额外的空格视为另一个单词的结束。这可能导致算法不会在最后一个实际单词后立即截断，而是在随后的一个或多个空格处截断。因此，如果截断位置正好位于这些额外空格之前，算法可能无法正确识别，并可能导致错误的输出。

如果 k 大于句子中的单词总数，算法的最后一步逻辑是直接返回整个句子，这在大多数情况下是正确的。然而，如果句子包含额外的尾随空格或连续空格，算法会将这些空格误认为单词分隔，从而可能在不恰当的位置结束。因此，在含有多余空格的特殊情况下，返回整个句子可能不符合预期的输出格式。

变量 `idx` 初始化为 None 是安全的，因为它是用来存储找到的截断位置的索引。在循环中，只有当找到截断位置（即 k 减到 0 时）才会给 `idx` 赋值。如果循环结束后 `idx` 仍为 None，表示没有找到截断位置，也就是说 k 大于句子中的单词总数，这时直接返回整个句子。这种做法在逻辑上是正确的，不会引发未预料的行为。