描述

一个不存在相邻的两个字符相同的字符串被称为差异字符串。
例如，“ababcb”、“a”和“abab”“ababcb”、“a”和“abab”是差异字符串，而“aaaaaa”、“abaa”和“bb“aaaaaa”、“abaa”和“bb”则不是。
给定一个只包含‘a‘ , ‘b‘ , ‘c‘ , ‘?‘ 四种字符的字符串，你需要用‘a‘ 、‘b‘ 或者‘c‘ 来替换 ‘?‘ 使 字符串成为差异字符串。

输入

第一行包含正整数t(1≤t ≤1000)测试数据的数量。
接下来每个用例一行，每行包含一个非空字符串S，仅由字符“a”、“b”、“c”和“?”组成。

输出

如果无法得到差异字符串，则输出“-1”(不带引号);
否则，输出替换所有‘?后的字符串。如果有多个答案，你可以输出任何一个。

样例

3
a???cb
a??bbc
a?b?c

ababcb
-1
acbac

提示

对于30%的数据：1≤len(S) ≤5
对于100%的数据：1 ≤|S| ≤10^5且T组用例S字符串长度总和不超过10^5

CODE

AC代码

#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for(int a = b; a <= c; a++)
#define dep(a, b, c) for(int a = b; a >= c; a--)
 
int t;
string s;

int main(){
	ios::sync_with_stdio(0); 
	cin >> t; 
	while(t--){
		cin >> s;
		rep(i, 0, s.length() - 1){
			if(s[i] == ‘?‘){
				if(s[i - 1] == ‘a‘){
					if(s[i + 1] == ‘a‘ || s[i + 1] == ‘c‘ || s[i + 1] == ‘?‘)
						s[i] = ‘b‘;
					if(s[i + 1] == ‘b‘)
						s[i] = ‘c‘;
				}
				else if(s[i - 1] == ‘b‘){
					if(s[i + 1] == ‘a‘ || s[i + 1] == ‘b‘ || s[i + 1] == ‘?‘)
						s[i] = ‘c‘;
					if(s[i + 1] == ‘c‘){
						s[i] = ‘a‘;
					}
				}else{
					if(s[i + 1] == ‘c‘ || s[i + 1] == ‘b‘ || s[i + 1] == ‘?‘)
						s[i] = ‘a‘;
					if(s[i + 1] == ‘a‘)
						s[i] = ‘b‘; 
				}
			}
		}
		bool check = 0;
		rep(i, 1, s.length() - 1){
			if(s[i] == s[i - 1]){
				check = 1;
			}
		} 
		if(check){
			cout << -1;
		}else{
			cout << s;
		}
		cout << endl;
	}
	return 0;
}

A-差异字符串

原文：https://www.cnblogs.com/Little-Turtle--QJY/p/13861143.html