题目:
给定一个只包含英文单词和空格的字符串和一个整数,设计算法将字符串分割成若干子串,每个子串的长度要小于等于。
要求每个子串只能通过空格来分割,不能切开单词。如果找不到解决方案,则返回空即可。你可以假定字符串的开头和结尾没有空格,并且每个单词之间有且仅有一个空格。
举例来说,给定字符串为,k = 10,则算法应该返回数组:。数组中所有子串的长度都不大于 10。
查看答案之前,独立思考一下解决方案会更好哦!
解析:
此题可以使用贪婪算法求解。首先我们将所有的单词拆解放到一个数组中,然后使用一个缓冲区作为当前的子串,尝试性地往里面添加单词,检查加入新的单词后长度是否满足要求。如果不满足要求,就可以直接把缓冲区的子串加入到结果数组中,然后重新开始新的子串。
注意如果任何单词的长度大于 k,则此问题是无解的,我们可以直接返回空。
代码如下:
我们会在每天上午10点左右推送一道高质量的编程题目,并给出该题目的参考答案以及详细的解析。
我们鼓励在经过独立思考和动手实践之后,再参考解析来查漏补缺。
领取专属 10元无门槛券
私享最新 技术干货