1816. Truncate Sentence
Description
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.
Solutions
Solution 1: Simulation
We traverse the string $s$ from the beginning. For the current character $s[i]$, if it is a space, we decrement $k$. When $k$ becomes $0$, it means that we have extracted $k$ words, so we return the substring $s[0..i)$.
After the traversal, we return $s$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. Ignoring the space complexity of the answer, the space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Solution 2
1 2 3 4 5 6 7 |
|