英文文本换行

题目:

给定一个只包含英文单词和空格的字符串和一个整数,设计算法将字符串分割成若干子串,每个子串的长度要小于等于。

要求每个子串只能通过空格来分割,不能切开单词。如果找不到解决方案,则返回空即可。你可以假定字符串的开头和结尾没有空格,并且每个单词之间有且仅有一个空格。

举例来说,给定字符串为,k = 10,则算法应该返回数组:。数组中所有子串的长度都不大于 10。

查看答案之前,独立思考一下解决方案会更好哦!

解析:

此题可以使用贪婪算法求解。首先我们将所有的单词拆解放到一个数组中,然后使用一个缓冲区作为当前的子串,尝试性地往里面添加单词,检查加入新的单词后长度是否满足要求。如果不满足要求,就可以直接把缓冲区的子串加入到结果数组中,然后重新开始新的子串。

注意如果任何单词的长度大于 k,则此问题是无解的,我们可以直接返回空。

代码如下:

我们会在每天上午10点左右推送一道高质量的编程题目,并给出该题目的参考答案以及详细的解析。

我们鼓励在经过独立思考和动手实践之后,再参考解析来查漏补缺。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181031G0HT9N00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券