How can I solve the 'Truncate Sentence' problem efficiently?

The most efficient solution involves converting the sentence into an array of words, slicing the array to the first k elements, and joining them back into a string.

What is the time complexity of the 'Truncate Sentence' problem?

The time complexity is O(n), where n is the length of the input string, due to the operations of splitting and joining the string.

How does converting a string to an array help in solving this problem?

Converting the string to an array simplifies truncation, as array slicing allows easy access to the first k words, which is harder to do with a raw string.

What is the space complexity of the solution?

The space complexity is O(n), where n is the length of the string, because we need to store the array of words.

How does this problem relate to common string manipulation techniques?

This problem involves common string manipulation techniques such as splitting, slicing, and joining, which are often used in more complex string-related challenges.

#1816

Easy

auto_awesome数组·string

LeetCode 题解工作台

截断句子

句子是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。每个单词仅由大小写英文字母组成（不含标点符号）。例如， "Hello World" 、 "HELLO" 和 "hello world hello world" 都是句子。给你一个句子 s 和一个整数 k …

数组字符串

题目描述

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

例如，"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 中的单词之间由单个空格隔开
不存在前导或尾随空格

lightbulb

解题思路

方法一：模拟

我们从前往后遍历字符串 $s$ ，对于当前遍历到的字符 $s[i]$ ，如果 $s[i]$ 是空格，那么 $k$ 自减 $1$ ，当 $k$ 为 $0$ 时，说明已经截取了 $k$ 个单词，截取字符串 $s[0..i)$ 返回即可。

遍历结束，返回 $s$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split()[:k])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should mention splitting the string into an array.
question_mark
Look for correct array slicing to ensure only the first k words are kept.
question_mark
Check if the candidate efficiently joins the sliced array back into a string.

warning

常见陷阱

外企场景

error
Misunderstanding the problem and trying to split or slice incorrectly.
error
Not handling edge cases such as k being equal to the number of words.
error
Forgetting to join the array back into a string after truncation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Truncate the sentence based on a different separator or delimiter.
arrow_right_alt
Extend the problem to allow truncation to any number of words and sentences.
arrow_right_alt
Handle cases where words are in different languages or character sets.

help

常见问题

外企场景

继续练习

#1813 句子相似性 III #1807 替换字符串中的括号内容 #1773 统计匹配检索规则的物品数量