2023-09-09 17:20 苏州大学 算法工程师
关注
笔试算法题-day06
题目：给定一个字符串集合，对于任意一个字符串A，从所有字符串中任取两个字符串B和C用于拼接为B+C，使得原始的字符串A可以通过B+C删除一个非空前缀和一个非空后缀得到，求出所有满足条件的字符串；
样例：s=["AABCD","BCDAA","BCD"]，"BCD"可以由s[0]+s[1]去掉前缀AA和后缀AA得到；
解题思路：
方法一：暴力法，对于所有字符串进行两两拼接构成一个集合，然后便利查询每个字符串是否可以通过集合中的字符串删除前缀和后缀得到，时间复杂度高，建立集合O(n^2)，遍历查询O(n*(n^2))，一共有n^2个字符串，遍历一次就是n^2;
大佬们有没有什么更好的解法，望赐教。
样例：s=["AABCD","BCDAA","BCD"]，"BCD"可以由s[0]+s[1]去掉前缀AA和后缀AA得到；
解题思路：
方法一：暴力法，对于所有字符串进行两两拼接构成一个集合，然后便利查询每个字符串是否可以通过集合中的字符串删除前缀和后缀得到，时间复杂度高，建立集合O(n^2)，遍历查询O(n*(n^2))，一共有n^2个字符串，遍历一次就是n^2;
大佬们有没有什么更好的解法，望赐教。
全部评论
相关推荐
点赞 评论 收藏
分享
11-01 17:40
门头沟学院 护士 
点赞 评论 收藏
分享