subject

Source: LeetCode https://leetcode-cn.com/problems/truncate-sentence

A sentence is a list of words separated by a single space, and there are no leading or trailing spaces. Each word consists of upper and lower case English letters only (excluding punctuation).

For example, "Hello World", "HELLO" and "Hello World" are sentences. Give you a sentence s and an integer K. please truncate s so that the truncated sentence contains only the first k words. Returns the sentence obtained after truncation s.

Example 1:

Enter: s = "hello how are you contentant", k = 4 Output: "Hello how are you" Explanation: The words in s are ["Hello", "how", "are", "you", "contentant"] The first four words are ["Hello", "how", "are", "you"] Therefore, "Hello how are you" should be returned

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 four words are ["What", "is", "the", "solution"] Therefore, "What is the solution" should be returned

Example 3:

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

Tips:

1 <= s.length <= 500 The value range of k is [number of words in 1, s] s consists only of upper and lower case letters and spaces The words in s are separated by a single space There are no leading or trailing spaces

solution

• Using library functions: s.split (''), '. Join (xxx)
• Previous traversal: initialize an empty string and count the number of spaces. The number of spaces encountered is + 1, and then splice the string. If the number of spaces is equal to k, break
• From the previous traversal, define an end, indicating that after the number of spaces k is satisfied, the position of end can be returned directly to s[:end]. One thing to note here is that k, if the value of k is equal to the number of words in s, it means to traverse to the end

Library function

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

Forward traversal + splicing

• python

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        n = len(s)
        ans = ''
        index = 0
        for i in range(n):
            if s[i]==' ':
                index += 1
            if index==k:
                break
            ans += s[i]
        return ans

• c++

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

From traversal + to cutoff subscript for why i==n is added to judge that the length of K is satisfied only after traversal, because the value range of K is [the number of words in 1, s], so there will be no case where k exceeds the number of words, and the number of spaces after traversal can be increased by one

• python

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        # ss = s.split(' ')
        # return ' '.join(ss[:k])
        n = len(s)
        end = 0
        index = 0
        for i in range(n+1):
            if i == n or s[i] == ' ':  # Note that N + 1 here, n means traversing to the end
                index += 1
                if index == k:
                    end = i
                    break
        return s[:i]

• c++

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

Complexity analysis

• Time complexity: O(N)
• Space complexity: O(1)