青海门户网站建设,移动互联网开发实践,企业网站制作排名,自媒体平台注册账号教程Problem: 2645. 构造有效字符串的最少插入数 文章目录 解题思路解决方法复杂度分析代码实现 解题思路
解决此问题需要确定如何以最小的插入次数构造一个有效的字符串。首先#xff0c;我们需要确定开头的差距#xff0c;然后决定中间的补足#xff0c;最后决定末尾的差距。… Problem: 2645. 构造有效字符串的最少插入数 文章目录 解题思路解决方法复杂度分析代码实现 解题思路
解决此问题需要确定如何以最小的插入次数构造一个有效的字符串。首先我们需要确定开头的差距然后决定中间的补足最后决定末尾的差距。
解决方法
在确定开头的差距时我们可以对字符a不进行任何处理b增加1c增加2。
对于中间位置的补足如果当前位置是a且下一个位置是b则不进行任何处理如果是c则增加1如果是a则增加2。同理如果当前位置是b且下一个位置是a1b2如果是c则b1c2。
对于末尾的差距c不处理b增加1a增加2。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中n是字符串的长度。这是因为我们需要遍历整个字符串来确定每个位置的最小插入次数。
空间复杂度 O ( 1 ) O(1) O(1)。这是因为我们只使用了几个变量来存储中间结果这些变量的大小是常数所以空间复杂度为O(1)。
代码实现
class Solution {
public:int addMinimum(string word) {int len word.size();int aMinimum 0;aMinimum abs(a - word[0]); // 开头a不处理aMinimum c - word[len - 1]; // 末尾c不处理for (int i 1; i len; i) { // 遍历中间字符if (word[i - 1] - word[i] -2 || word[i - 1] - word[i] 1) { // 下一个字符与当前字符相差-2或1不处理aMinimum 1;} else if (word[i - 1] word[i]) { // 下一个字符与当前字符相同需要增加2或者1aMinimum 2;} else { // 下一个字符与当前字符不同且相差大于1需要增加1aMinimum 1;}}return aMinimum; // 返回最小插入次数}
};
