丑陋的字符串

喜欢ヅ旅行 2022-06-13 08:43 141阅读 0赞

**\[编程题5\]丑陋的字符串**

**牛牛喜欢字符串,但是他讨厌丑陋的字符串。对于牛牛来说,一个字符串的丑陋值是字符串中相同连续字符对的个数。比如字符串“ABABAABBB”的丑陋值是3,因为有一对"AA"和两对重叠的"BB"。现在给出一个字符串,字符串中包含字符'A'、'B'和'?'。牛牛现在可以把字符串中的问号改为'A'或者'B'。牛牛现在想让字符串的丑陋值最小,希望你能帮帮他。 **

##### 输入描述: #####

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包含'A','B','?'三种字符。

##### 输出描述: #####

输出一个整数,表示最小的丑陋值

示例1

## 输入 ##

A?A

## 输出 ##

**分析思路:**

如果字符串里面全部是‘A’或‘B’问题就会非常简单，现在多了'？'这个字符，而且可以变为‘A’或‘B’。那我们想是不是可以把所有的'?'变为'A'或'B'呢？依据是什么呢？

我们先看一个例子，假设有字符串S：“**？？？ABB？？？A？？？**”。

前面连续是三个？，如何确定其值呢，因为最终是两两比较的，所以前面几个连续的'?'我们不需要管，当求最小的丑陋值时，我们只需要从第一个不是'?'开始的字符（A）开始就行了，因为前面我们总可以让其设为每对值不同，如**BAB**ABB？？？A？？？，记原序列中第一非'？'位置的字符A位置为pos，我们从pos下一位置开始遍历，索引记为i，当遇到'?'时，我们就看其前面一个位置（非'?'）的字符是什么，若为S\[i-1\]='A',则令当前位置S\[i\]=’B‘，否则令当前位置S\[i\]=’A‘。依次往后遍历，这样第一非’？‘后面所有的’？‘都会被替换为具体的字符了，而且可以保证丑陋值最小。

最后从S中的pos位置开始遍历，判断每对字符是否相等就行了。

**参考代码：**

#include<iostream>
    using namespace std;
    int calAugly(string s,int pos)
      {
         int length=s.size();
         int count=0;
         for(int i=pos+1;i<length;i++)
           {
              if(s[i]==s[i-1])
                  count++;
           }
        return count;
      }
    
    int main()
      {
         string s;
         while(cin>>s)
           {
              int length=s.size();
              int pos=0;
              while(pos<length&&s[pos]=='?')
                  pos++;
              for(int i=pos+1;i<length;i++)
                {
                   if(s[i]=='?') 
                     {
                        if(s[i-1]=='A')
                            s[i]='B';
                        else
                            s[i]='A';
                     }
                }
              int count=calAugly(s,pos);
              cout<<count<<endl;
           }
      }