提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

leetcode每日一题：1816. 截断句子

2023-04-18 14:45:00 时间

题目

来源：力扣（LeetCode） https://leetcode-cn.com/problems/truncate-sentence

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

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

解法

  • 利用库函数:s.split(' '), ' '.join(xxx)
  • 从前遍历：初始化一个空字符串以及统计空格出现的次数，遇到空格次数+1，之后就拼接字符串，如果空格次数等于k，则break
  • 从前遍历，定义一个end，表明满足空格次数k后，end的位置，直接返回s[:end]即可。这里有一点要注意k，如果k的取值等于s中单词的数目时候，表明要遍历到最后

库函数

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

从前遍历+拼接

  • 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;
    }
};

从前遍历+定位到截止下标 for 为什么添加i==n 是为了判断遍历完了 才满足k的长度， 因为k 的取值范围是 [1, s 中单词的数目]， 因此不会出现那种k超过单词数目的情况，遍历完了空格数也加一即可

  • 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] == ' ':  # 注意这里的n+1, n表示遍历到了最后
                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);
    }
};

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(1)

相关文章