力扣每日一题 2625.构造有效字符串的最少插入数

发布时间:2024年01月14日

给你一个字符串?word?,你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次,返回使?word?有效?需要插入的最少字母数。

如果字符串可以由 "abc" 串联多次得到,则认为该字符串?有效?。

解法:双指针做法,有连续的abc是不需要增添的,那么可以把字符串把"abc"当作分隔符分隔出若干个子串,对每个子串求插入字母数。

接下来对每个子串求解:

分类讨论,判断当前字符和下一个字符能否构成"ab","bc","ac"中的其中一个,如果可以的话,当前就只需要添加一个字符,并且指针继续向后移动两位继续遍历。

如果不可以,那么当前字符就得添两次,然后两个指针都向后移动一位继续遍历。

注意:对每个子串末尾添加一个任意字符(不要是abc就行),因为有可能子串的最后一个字符是单独一组的,当左指针在最后一位时,右指针越界了,无法进行判断。

AC代码

class Solution {
public:
    int addMinimum(string word) {
        vector<string>words;
        for(int i = 0 ,j=0; i<word.size();i++ )
        {
         if(word[i]=='a'&& word[i+1]=='b' &&word[i+2]=='c')
            {
                string s = word.substr(j,i-j);
                if(s!="")
                words.push_back(s);
                j=i+3;
                i=i+2;
                continue;
            }
            if(j<word.size()&&i==word.size()-1)
            {        
                string s= word.substr(j);
                if(s!="")
                words.push_back(s);
            }
        }   
        int res=0;
        for(int k=0;k<words.size();k++)
        {
            string str = words[k];
           // cout<<str<<endl;
            int i=0,j=1;
            str+='z';
            if(str.size()>2)
            {
                while(j<str.size())
                {
                    if(str[i]=='a'&&str[j]=='b' || str[i] =='a'&&str[j]=='c' || str[i]=='b'&&str[j]=='c')
                    {
                        res++;
                        i=j+1;
                        j+=2;
                    }
                    else
                    {
                        res+=2;
                        i++;
                        j++;
                    }
                }
            }
            else 
                res+=2;
        }
        return res;
    }
};

文章来源:https://blog.csdn.net/weixin_63022020/article/details/135535585
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。