1816. 截断句子

🟢   🔖  数组 字符串  🔗 力扣 LeetCode

题目

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).

• For example, "Hello World", "HELLO", and "hello world hello world" are all sentences.

You are given a sentence s​​​​​​ and an integer k​​​​​​. You want to truncate s​​​​​​ such that it contains only the first k​​​​​​ words. Return s​​​​ ​​ after truncating it.

Example 1:

Input: s = "Hello how are you Contestant", k = 4

Output: "Hello how are you"

Explanation:

The words in s are ["Hello", "how" "are", "you", "Contestant"].

The first 4 words are ["Hello", "how", "are", "you"].

Hence, you should return "Hello how are you".

Example 2:

Input: s = "What is the solution to this problem", k = 4

Output: "What is the solution"

Explanation:

The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].

The first 4 words are ["What", "is", "the", "solution"].

Hence, you should return "What is the solution".

Example 3:

Input: s = "chopper is not a tanuki", k = 5

Output: "chopper is not a tanuki"

Constraints:

• 1 <= s.length <= 500
• k is in the range [1, the number of words in s].
• s consist of only lowercase and uppercase English letters and spaces.
• The words in s are separated by a single space.
• There are no leading or trailing spaces.

题目大意

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

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

解题思路

思路一：分割字符串

1. 分割字符串：可以使用 JavaScript 的 split(' ') 方法把字符串按空格分割成单词数组。
2. 截取前 k 个单词：使用数组的 slice(0, k) 方法截取前 k 个单词。
3. 重新组合字符串：使用 join(' ') 将前 k 个单词重新组合成字符串，单词之间以空格分隔。

复杂度分析

• 时间复杂度: O(n)，其中 n 是字符串 s 的长度。因为需要遍历整个字符串进行分割，且数组的切割操作和连接操作也是线性的。
• 空间复杂度: O(n)，由于需要存储分割后的单词数组，空间复杂度为 O(n)。

---

思路二：逐个遍历

虽然使用 split() 和 slice() 的方法已经很高效，但我们可以进一步优化空间复杂度，避免创建多余的数组。

• 减少时间消耗：通过遍历字符串，逐个读取单词并计数，直到获取 k 个单词为止。这样不需要将整个字符串拆分为单词数组，只需要遍历到第 k 个单词时停止，减少了时间开销。
• 减少内存消耗：避免创建数组并直接构建最终结果字符串，边遍历边构建。

1. 变量初始化：使用 wordCount 计数当前已经读取的单词数，result 存储拼接的结果。
2. 遍历字符串：逐个字符遍历字符串：
   • 如果遇到空格并且已经获取了 k 个单词，则停止遍历。
   • 如果遇到空格，则说明一个单词读取完毕，增加 wordCount。
   • 否则，继续拼接字符到 result 中。
3. 返回结果：当 wordCount 达到 k 后，直接返回拼接的结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。最坏情况下，仍然需要遍历原字符串一次，
• 空间复杂度：O(1)，除了存储结果字符串外，不需要额外的数组存储中间结果。

代码

分割字符串

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var truncateSentence = function (s, k) {
	return s.split(' ').slice(0, k).join(' ');
};

逐个遍历

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var truncateSentence = function (s, k) {
	let wordCount = 0;
	let result = '';

	for (let i = 0; i < s.length; i++) {
		if (s[i] === ' ' && wordCount === k) break;
		if (s[i] === ' ') wordCount++;
		if (wordCount < k) result += s[i];
	}

	return result;
};