1816. 截断句子

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 中的单词由单个空格分隔
• 没有前导或尾随空格

解题思路

这道题要求我们从句子中截取前 k 个单词。主要有两种解法思路：

方法一：字符串分割法 将句子按空格分割成单词数组，然后取前 k 个单词重新组合成句子。这种方法思路清晰，代码简洁，但需要额外的空间存储分割后的单词数组。

方法二：一次遍历法（推荐） 遍历字符串，统计空格的数量来确定单词边界。当遇到第 k 个空格时，说明已经找到了前 k 个单词的结束位置。这种方法只需要 O(1) 的额外空间，效率更高。

对于方法二的实现：我们从左到右遍历字符串，每遇到一个空格就将计数器加 1。当计数器达到 k 时，说明我们已经找到了前 k 个单词，此时截取从开始到当前位置的子字符串即可。需要注意边界情况：如果 k 等于总单词数，则返回原字符串。

两种方法的时间复杂度都是 O(n)，但方法二的空间复杂度更优，是实际应用中的首选方案。

代码实现

class Solution {
public:
    string truncateSentence(string s, int k) {
        int spaceCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                spaceCount++;
                if (spaceCount == k) {
                    return s.substr(0, i);
                }
            }
        }
        return s;
    }
};

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        space_count = 0
        for i, char in enumerate(s):
            if char == ' ':
                space_count += 1
                if space_count == k:
                    return s[:i]
        return s

public class Solution {
    public string TruncateSentence(string s, int k) {
        int spaceCount = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == ' ') {
                spaceCount++;
                if (spaceCount == k) {
                    return s.Substring(0, i);
                }
            }
        }
        return s;
    }
}

var truncateSentence = function(s, k) {
    let spaceCount = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i]

复杂度分析

其中 n 是字符串 s 的长度。一次遍历法在空间复杂度上更优，是推荐的解法。