给定长度为N的字符串S，返回一个由将字符串S中的每个'?'替换为'a'或'b'字符的结果组成的字符串，并且该字符串不包含连续三个相同的字母（换句话说，处理后的字符串中既不允许出现'aaa'也不允许出现'bbb'）。
示例：
Given S="a?bb", output= "aabb"
Given S="??abb", output= "ababb" or "bbabb" or "baabb"
Given S="a?b?aa", output= "aabbaa"
1≤n≤500000
我使用回溯法解决了这个问题，但我的解决方案很慢，并且对于更大的N值不起作用，有更好的方法吗？
?的x??y总是有效的。
a??b => abab（在两侧都不会增加长度，*后面不受影响*）a??a => abba（没有影响）a???????????????????b => ab?????????????????ab?的情况。
aa? => aab（没有其他可能性）a?a => aba（没有影响）a?b中。
aa?b => aabb（如aa?中所述）ba?b => baab（没有影响）^a?b => ^aab（仅适用于开头，没有影响）O(n)的解决方案。O(n)检查。
我在我的另一个答案中添加了可能的实现。（请参考我的贪心算法的O(n)时间复杂度，O(1)空间复杂度的解决方案，其中包括随机测试，与MTO的代码进行比较。）
O(n)动态规划有四个状态：一个字符可以是a_first、a_second、b_first或b_second。令dp[i]表示创建有效字符串的可能性，直到索引i。然后：
dp[i][a_first] = True
dp[i][a_second] = True
dp[i][b_first] = True
dp[i][b_second] = True
where i < 0
if s[i] == '?':
dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
dp[i][a_second] = dp[i-1][a_first]
dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
dp[i][b_second] = dp[i-1][b_first]
else if s[i] == 'a':
dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
dp[i][a_second] = dp[i-1][a_first]
dp[i][b_first] = False
dp[i][b_second] = False
else:
dp[i][a_first] = False
dp[i][a_second] = False
dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
dp[i][b_second] = dp[i-1][b_first]
where i ≥ 0
要获取字符串，我们可以沿着保持True的路径向后跟随，并保持连续字符约束。
Python代码：
def f(s):
dp = [[None] * 4 for _ in range(len(s))]
def get_dp(i, j):
return True if i < 0 else dp[i][j]
for i in range(len(s)):
if s[i] == '?':
dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
dp[i][1] = get_dp(i-1, 0)
dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
dp[i][3] = get_dp(i-1, 2)
elif s[i] == 'a':
dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
dp[i][1] = get_dp(i-1, 0)
dp[i][2] = False
dp[i][3] = False
else:
dp[i][0] = False
dp[i][1] = False
dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
dp[i][3] = get_dp(i-1, 2)
# Build the output
result = []
i = len(s) - 1
need = None
while i >= 0:
if dp[i][0] and need != 'b':
result.append('a')
need = None if (len(result) == 1 or result[-2] == 'b') else 'b'
i-= 1
elif dp[i][1] and need != 'b':
result.extend(['a', 'a'])
need = 'b'
i -= 2
elif dp[i][2] and need != 'a':
result.append('b')
need = None if (len(result) == 1 or result[-2] == 'a') else 'a'
i -= 1
elif dp[i][3] and need != 'a':
result.extend(['b', 'b'])
need = 'a'
i -= 2
else:
return ""
return "".join(reversed(result))
输出：
strs = [
"a?bb", # "aabb"
"??abb", # "ababb" or "bbabb" or "baabb"
"a?b?aa", # "aabbaa"
"?bb?",
"aa?bb", # NO SOLUTION
"aa??aa", # "aabbaa"
"ab???bb?",
"????",
"??",
"?????",
"??????"
]
for s in strs:
print("%s\n%s\n" % (s, f(s)))
"""
a?bb
aabb
??abb
baabb
a?b?aa
aabbaa
?bb?
abba
aa?bb
aa??aa
aabbaa
ab???bb?
abbaabba
????
abaa
??
aa
?????
aabaa
??????
baabaa
"""
i 的字符是否可以是“第一个 a”、“第二个 a”、“第一个 b”或“第二个 b”。例如，只有在前一个字符可以是“第一个 a”的情况下，当前字符才能是“第二个 a”——尝试遵循类似的常识逻辑来理解其他状态的条件。 - גלעד ברקן我回答中提到的规则的可能实现方式。
该实现:
O(n) 时间复杂度O(1)首先合并规则：
a?? => ab?
a??b => abab (a??b => ab?b => abab)a??a => abbaa???????????????????b => ab??????????????????bba?b => baab^a?b => ^aaba? => ab(也意味着a??)
aa? => aaba?a => abaaa?b => aabb然后设置边界条件。
规则需要字符串不以?开头(如果简单地在另一个遍历中填充它们，则无需此操作)
^?? => a?(就好像我们在前面加了一个b)^?a => ba针对a?b，规则需要2个回望，因此我只需预先应用它即可防止主循环内的检查
^a?b => ^aab代码 (WandBox 链接)
char inverse(char c){return c=='a'?'b':'a';}
std::string solve(std::string s){
/// boundary conditions
if(s.size()<3){
for(auto& c:s) if(c=='?') c='b';
return s;
}
if(s.starts_with("??")) s[0]='a'; // ?? => a? // not really necessary if use another pass to fill prefix '?'s
if(s.starts_with("?a") || s.starts_with("?b")) s[0]=inverse(s[1]); // ?a => ba // not really necessary as above
if(s.starts_with("a??") || s.starts_with("b??")) s[1]=inverse(s[0]); // not really necessary, just to prevent access s[-1]
if(s.starts_with("a?b") || s.starts_with("b?a")) s[1]=s[0]; // ^a?b => aab
/// primary loop
for(auto curr=s.data(); curr!=s.data()+s.size(); ++curr)
if(*curr=='?'){
if(curr[-1]!=curr[1] && curr[-2]==curr[1]) *curr=curr[-1]; // ba?b => baab
else *curr = inverse(curr[-1]); // a? => b (rule coaslesing)
}
return s;
}
isValid 仅检查在位置 pos 插入字符 c 是否会引起问题，而不是迭代整个字符串；
维护一个变量 int dir = +-1 来知道我们是否向前或向后移动字符串（这只是很重要，以便我们在跳过原始字符串中的非 ? 字符时知道应该向哪个方向移动）；
通过判断，使用 if / else if / else 树来确定 we're at(我们所处的情况) （跳过非 ? 的字符，或者新的 ? 向前，或者已经尝试了 a，或者已经尝试了 a 和 b ）；
solve 有一个布尔返回值，如果找到解决方案，则为 true （pos == s.length()），如果未找到解决方案，则为 false （pos == (unsigned int) -1）。
#include <iostream>
#include <vector>
bool isValid(char c, std::string const &s, unsigned int pos)
{
return ((pos < 2 || s[pos - 2] != c || s[pos - 1] != c)
&& (pos < 1 || pos + 1 >= s.length() || s[pos - 1] != c || s[pos + 1] != c)
&& (pos + 2 >= s.length() || s[pos + 1] != c || s[pos + 2] != c));
}
bool solve(std::string const &in, std::string &out)
{
unsigned int pos = 0;
int dir = 1;
out = in;
while (pos < in.size())
{
if (in[pos] != '?') // nothing to do: keep moving (forward or backward)
{
pos += dir;
}
else if (out[pos] == '?') // going forward, will try 'a' then 'b'
{
dir = 1;
if (isValid('a', out, pos))
{
out[pos] = 'a';
pos += dir;
}
else if (isValid('b', out, pos))
{
out[pos] = 'b';
pos += dir;
}
else
{
dir = -1;
pos += dir;
}
}
else if (out[pos] == 'a' && isValid('b', out, pos)) // going backward, already tried 'a'
{
out[pos] = 'b';
dir = 1;
pos += dir;
}
else // already tried everything: backtrack
{
dir = -1;
out[pos] = '?';
pos += dir;
}
}
return (pos == in.size());
}
int main(void)
{
std::vector<std::string> ins = {"a?bb", "??abb", "a?b?aa", "aa?bb"};
std::vector<std::string> outs = {"", "", "", "", ""};
for (unsigned int i = 0; i < ins.size(); ++i)
{
if (solve(ins[i], outs[i]))
std::cout << ins[i] << " --> " << outs[i] << std::endl;
else
std::cout << ins[i] << " --> NO SOLUTION" << std::endl;
}
return 0;
}
输出：
a?bb --> aabb
??abb --> ababb
a?b?aa --> aabbaa
aa?bb --> NO SOLUTION
实现@appleapple的O(N)解决方案在JavaScript中（但是相对简单地移植到C ++）：
let solve = (str) => {
let opposite = {"a":"b","b":"a"};
let curr_idx = 0;
let output = [];
let lookahead = (x) => ((curr_idx+x<0)||(curr_idx+x>=str.length)?null:str[curr_idx + x]);
let lookbehind = (x) => (curr_idx-x<0?null:output[curr_idx - x])
let matches = (x,y) => (x == y || x == null || y == null);
let is_replacement = (x) => (x == '?');
while ( curr_idx < str.length )
{
let curr = lookbehind(1) || 'b';
let i = 0;
let next = lookahead(i);
while (is_replacement(next))
{
++i;
next = lookahead(i);
}
if (next == null)
{
// Found the end of the string.
// Append characters opposite to the previous for each ?
for (; i > 0; --i)
{
curr = opposite[curr];
output.push( curr );
}
break;
}
if (i > 1)
{
// Found multiple successive ?s
// Handle the first half of the ?s by
// Append alternating characters from the previous character.
let j = 0;
for (; j < i/ 2; ++j)
{
curr = opposite[curr];
output.push( curr );
}
// Then handle the second half of the ?s
// append alternating characters to the next character after the ?s.
for (; j < i; ++j)
{
output.push( (j%2) == (i%2) ? next : opposite[next] );
}
}
else if (i == 1)
{
// Found a single ?
let prev = lookbehind(2);
if (curr == prev && curr == opposite[next] && next == lookahead(2))
{
// No solution.
return null;
}
if (curr == prev || matches(curr, next))
{
output.push( opposite[curr] );
}
else
{
output.push( curr );
}
}
if ( next != null )
{
// Output the next non-? character.
output.push( next );
}
curr_idx += i + 1;
}
return output.join("");
};
let tests = [
"?",
"a?",
"a??",
"a???",
"b?",
"b??",
"b???",
"a?a",
"a?b",
"b?a",
"b?b",
"a??a",
"a??b",
"b??a",
"b??b",
"aa?",
"ba?",
"a?bb",
"?bb?",
"??abb",
"a?b?aa",
"ab???bb?",
"aa?bb",
];
for ( let test of tests )
{
console.log( `${test} -> ${solve(test)}` );
}可以将问题简化为10个从左到右操作字符串的规则，查看最大窗口为6个字符（2个向后查找和4个向前查找），这些规则可以生成字符串的所有可能解决方案：
Rules:
0: ss?dd_ -> No solution
1: __??ss -> __?dss
2: _s?s__ -> _sds__
3: ss?___ -> ssd___
4: __?ss_ -> __dss_
5: DS?DS_ -> DSsDS_ | DSdDS_
6: DS??sD -> DSsdsD | DSddsD | DSdssD
7: Ds??dS -> DsdsdS | DssddS
8: ^??X_ -> ^s?X_ | ^d?X_
9: Ds??X_ -> DssdX_ | Dsd?X_
Notations:
s: Same character.
d: The opposite of the same character.
S: Either the same character or the end-of-the-string.
D: Either the opposite of the same character or the start- or end-of-the-string.
_: Any character or the start- or end-of-the-string.
?: A character to replace.
X: Either a character to replace or the end-of-the-string.
^: The start-of-the-string.
function* solve(
str,
i = 0,
depth = 0
)
{
let data = Array.from(str);
let chr = (n) => (n < 0 || n > data.length ? null : data[n]);
let lookbehind2 = chr(i - 2);
let lookbehind1 = chr(i - 1);
let current = chr(i);
let lookahead1 = chr(i + 1);
let lookahead2 = chr(i + 2);
let lookahead3 = chr(i + 3);
const DEBUG = (rule) => {
if (false)
{
console.log(`${"".padStart(depth)}Rule ${rule}@${i}: ${str} -> ${data.join("")}`)
}
};
let stepForward = (steps) => {
for (let n = 0; n < steps; ++n)
{
++i;
lookbehind2 = lookbehind1;
lookbehind1 = current;
current = lookahead1;
lookahead1 = lookahead2;
lookahead2 = lookahead3;
lookahead3 = chr(i + 3);
}
}
let isSolved = (ch) => (ch == 'a' || ch == 'b');
let isSame = (ch1, ch2) => (isSolved(ch1) && ch1 == ch2);
let opposite = (ch) => ({"a":"b","b":"a"}[ch]);
let isOpposite = (ch1, ch2) => (isSolved(ch1) && ch1 == opposite(ch2));
let isEndOfString = (ch) => (ch == null);
let isStartOfString = (ch) => (ch == null);
while( !isEndOfString(current) )
{
if (current != '?')
{
stepForward(1);
continue;
}
// Rules:
// 0: ss?dd_ -> No solution
// 1: __??ss -> __?dss
// 2: _s?s__ -> _sds__
// 3: ss?___ -> ssd___
// 4: __?ss_ -> __dss_
// 5: DS?DS_ -> DSsDS_ | DSdDS_
// 6: DS??sD -> DSsdsD | DSddsD | DSdssD
// 7: Ds??dS -> DsdsdS | DssddS
// 8: $??X_ -> $s?X_ | $d?X_
// 9: Ds??X_ -> DssdX_ | Dsd?X_
//
// Notations:
// s: Same character.
// d: The opposite of the same character.
// S: Either the same character or the end-of-the-string.
// D: Either the opposite of the same character or the start- or end-of-the-string.
// _: Any character or the start- or end-of-the-string.
// ?: A character to replace.
// X: Either a character to replace or the end-of-the-string.
// $: The end-of-the-string.
// -----------------------------------------------------------
// Rule 0: ss?dd_ -> No solution
if (
isSame(lookbehind2, lookbehind1)
&& isSame(lookahead1, lookahead2)
&& lookbehind1 != lookahead1
)
{
DEBUG(0);
return;
}
// Rule 1: __??ss -> __?dss
if (lookahead1 == '?' && isSame(lookahead2, lookahead3))
{
data[i + 1] = lookahead1 = opposite(lookahead2);
DEBUG(1);
}
// Rule 2: _s?s__ -> _sds__
if (isSame(lookbehind1, lookahead1))
{
data[i] = current = opposite(lookahead1);
DEBUG(2);
stepForward(2);
continue;
}
// Rule 3: ss?___ -> ssd___
if (isSame(lookbehind2, lookbehind1))
{
data[i] = current = opposite(lookbehind1);
DEBUG(3);
stepForward(1);
continue;
}
// Rule 4: __?ss_ -> __dss_
if (isSame(lookahead1, lookahead2))
{
data[i] = current = opposite(lookahead1);
DEBUG(4);
stepForward(3);
continue;
}
// Rule 5: DS?DS_ -> DSsDS_ | DSdDS_
if (lookahead1 != '?')
{
data[i] = current = "a";
DEBUG(5);
for (solution of solve(data.join(""), i + 2, depth + 1))
{
yield solution;
}
data[i] = current = "b";
DEBUG(5);
for (solution of solve(data.join(""), i + 2, depth + 1))
{
yield solution;
}
return;
}
// Rule 6: DS??sD -> DSsdsD | DSddsD | DSdssD
if (
isSame(lookbehind1, lookahead2)
|| (isStartOfString(lookbehind1) && isSolved(lookahead2))
)
{
data[i] = current = lookahead2;
data[i+1] = lookahead1 = opposite(lookahead2);
DEBUG(6);
for (solution of solve(data.join(""), i + 3, depth + 1))
{
yield solution;
}
data[i] = current = opposite(lookahead2);
data[i+1] = lookahead1 = opposite(lookahead2);
DEBUG(6);
for (solution of solve(data.join(""), i + 3, depth + 1))
{
yield solution;
}
data[i] = current = opposite(lookahead2);
data[i+1] = lookahead1 = lookahead2;
DEBUG(6);
for (solution of solve(data.join(""), i + 3, depth + 1))
{
yield solution;
}
return;
}
// Rule 7: Ds??dS -> DsdsdS | DssddS
if (isOpposite(lookahead2, lookbehind1))
{
data[i] = current = lookahead2;
data[i+1] = lookahead1 = opposite(lookahead2);
DEBUG(7);
for (solution of solve(data.join(""), i + 3, depth + 1))
{
yield solution;
}
data[i] = current = opposite(lookahead2);
data[i+1] = lookahead1 = lookahead2;
DEBUG(7);
for (solution of solve(data.join(""), i + 3, depth + 1))
{
yield solution;
}
return;
}
// Rule 8: $??X_ -> $s?X_ | $d?X_
// Rule 9: Ds??X_ -> DssdX_ | Dsd?X_
if (lookahead2 == "?" || isEndOfString(lookahead2))
{
if (isStartOfString(lookbehind1))
{
data[i] = current = "a";
DEBUG(8);
for (solution of solve(data.join(""), i + 1, depth + 1))
{
yield solution;
}
data[i] = current = "b";
DEBUG(8);
for (solution of solve(data.join(""), i + 1, depth + 1))
{
yield solution;
}
}
else
{
data[i] = current = opposite(lookbehind1);
DEBUG(9);
for (solution of solve(data.join(""), i + 1, depth + 1))
{
yield solution;
}
data[i] = current = lookbehind1;
data[i+1] = lookahead1 = opposite(lookbehind1);
DEBUG(9);
for (solution of solve(data.join(""), i + 2, depth + 1))
{
yield solution;
}
}
return;
}
throw `Invalid state ${data.join("")}`;
}
yield data.join("");
}
let tests = [
"?",
"??",
"???",
"a?",
"a??",
"a???",
"b?",
"b??",
"b???",
"a?a",
"a?b",
"b?a",
"b?b",
"a??a",
"a??b",
"b??a",
"b??b",
"aa?",
"ba?",
"a?bb",
"?bb?",
"?a",
"?aa",
"??aa",
"???aa",
"????aa",
"?ab",
"??ab",
"???ab",
"????ab",
"a?b?aa",
"ab???bb?",
"aa?bb",
"a?b?a?bb",
"?a?b?aa",
];
for ( let test of tests )
{
console.log( `${test} -> ${[...solve(test)]}` );
}#include <iostream>
#include <list>
class PartialSolution
{
public:
const std::string partial_solution;
const int position;
PartialSolution(
std::string const &solution,
const int pos
):
partial_solution(solution),
position(pos)
{}
};
class Solver
{
const bool DEBUGGING = false;
std::string str;
int position;
char lookbehind2;
char lookbehind1;
char current;
char lookahead1;
char lookahead2;
char lookahead3;
char get_character(int pos) const
{
if ( pos < 0 || pos >= str.length() )
{
return '\0';
}
return str[pos];
}
void load_partial_solution(PartialSolution const &ps)
{
str = ps.partial_solution;
position = ps.position;
lookbehind2 = get_character(position - 2);
lookbehind1 = get_character(position - 1);
current = get_character(position + 0);
lookahead1 = get_character(position + 1);
lookahead2 = get_character(position + 2);
lookahead3 = get_character(position + 3);
if (DEBUGGING)
{
std::cout << "Load @" << position << ": " << str << "\n";
}
}
void step_forward(int n)
{
for (int i = 0; i < n; ++i)
{
++position;
lookbehind2 = lookbehind1;
lookbehind1 = current;
current = lookahead1;
lookahead1 = lookahead2;
lookahead2 = lookahead3;
lookahead3 = get_character(position + 3);
}
}
bool is_solved(char ch) const
{
return ch == 'a' || ch == 'b';
}
bool is_same(char ch1, char ch2) const
{
return is_solved(ch1) && ch1 == ch2;
}
char opposite(char ch) const
{
switch(ch)
{
case 'a': return 'b';
case 'b': return 'a';
default:
return '\0';
}
}
bool is_opposite(char ch1, char ch2) const
{
return is_solved(ch1) && ch1 == opposite(ch2);
}
bool is_end_of_string(char ch) const
{
return ch == '\0';
}
bool is_start_of_string(char ch) const
{
return ch == '\0';
}
void DEBUG(int rule, bool pushback = false) const
{
if (DEBUGGING)
{
std::cout << (pushback?"Save: ":"") << "Rule " << rule << "@" << position << ": " << str << "\n";
}
}
public:
std::list<std::string> solve(std::string const&);
};
std::list<std::string> Solver::solve(std::string const& data)
{
std::list<PartialSolution> partial_solutions = { PartialSolution(data, 0) };
std::list<std::string> solutions = {};
while( !partial_solutions.empty() )
{
load_partial_solution( partial_solutions.back() );
partial_solutions.pop_back();
while( !is_end_of_string(current) )
{
if (current != '?')
{
step_forward(1);
continue;
}
// Rules:
// 0: ss?dd_ -> No solution
// 1: __??ss -> __?dss
// 2: _s?s__ -> _sds__
// 3: ss?___ -> ssd___
// 4: __?ss_ -> __dss_
// 5: DS?DS_ -> DSsDS_ | DSdDS_
// 6: DS??sD -> DSsdsD | DSddsD | DSdssD
// 7: Ds??dS -> DsdsdS | DssddS
// 8: $??X_ -> $s?X_ | $d?X_
// 9: Ds??X_ -> DssdX_ | Dsd?X_
//
// Notations:
// s: Same character.
// d: The opposite of the same character.
// S: Either the same character or the end-of-the-string.
// D: Either the opposite of the same character or the start- or end-of-the-string.
// _: Any character or the start- or end-of-the-string.
// ?: A character to replace.
// X: Either a character to replace or the end-of-the-string.
// $: The end-of-the-string.
// -----------------------------------------------------------
// Rule 0: ss?dd_ -> No solution
if (
is_same(lookbehind2, lookbehind1)
&& is_same(lookahead1, lookahead2)
&& lookbehind1 != lookahead1
)
{
DEBUG(0);
goto no_solution;
}
// Rule 1: __??ss -> __?dss
if (lookahead1 == '?' && is_same(lookahead2, lookahead3))
{
lookahead1 = opposite(lookahead2);
str[position+1] = lookahead1;
DEBUG(1);
}
// Rule 2: _s?s__ -> _sds__
if (is_same(lookbehind1, lookahead1))
{
str[position] = current = opposite(lookahead1);
DEBUG(2);
step_forward(2);
continue;
}
// Rule 3: ss?___ -> ssd___
if (is_same(lookbehind2, lookbehind1))
{
str[position] = current = opposite(lookbehind1);
DEBUG(3);
step_forward(1);
continue;
}
// Rule 4: __?ss_ -> __dss_
if (is_same(lookahead1, lookahead2))
{
str[position] = current = opposite(lookahead1);
DEBUG(4);
step_forward(3);
continue;
}
// Rule 5: DS?DS_ -> DSsDS_ | DSdDS_
if (lookahead1 != '?')
{
str[position] = current = 'b';
DEBUG(5, true);
partial_solutions.emplace_back(str, position + 2);
str[position] = current = 'a';
DEBUG(5);
step_forward(2);
continue;
}
// Rule 6: DS??sD -> DSsdsD | DSddsD | DSdssD
if (
is_same(lookbehind1, lookahead2)
|| (is_start_of_string(lookbehind1) && is_solved(lookahead2))
)
{
str[position] = current = opposite(lookahead2);
str[position+1] = lookahead1 = lookahead2;
DEBUG(6, true);
partial_solutions.emplace_back(str, position + 3);
str[position] = current = opposite(lookahead2);
str[position+1] = lookahead1 = opposite(lookahead2);
DEBUG(6, true);
partial_solutions.emplace_back(str, position + 3);
str[position] = current = lookahead2;
str[position+1] = lookahead1 = opposite(lookahead2);
DEBUG(6);
step_forward(3);
continue;
}
// Rule 7: Ds??dS -> DsdsdS | DssddS
if (is_opposite(lookahead2, lookbehind1))
{
str[position] = current = opposite(lookahead2);
str[position+1] = lookahead1 = lookahead2;
DEBUG(7, true);
partial_solutions.emplace_back(str, position + 3);
str[position] = current = lookahead2;
str[position+1] = lookahead1 = opposite(lookahead2);
DEBUG(7);
step_forward(3);
continue;
}
// Rule 8: $??X_ -> $s?X_ | $d?X_
// Rule 9: Ds??X_ -> DssdX_ | Dsd?X_
if (lookahead2 == '?' || is_end_of_string(lookahead2))
{
if (is_start_of_string(lookbehind1))
{
str[position] = current = 'b';
DEBUG(8, true);
partial_solutions.emplace_back(str, position + 1);
str[position] = current = 'a';
DEBUG(8);
step_forward(1);
continue;
}
else
{
str[position] = current = lookbehind1;
str[position+1] = lookahead1 = opposite(lookbehind1);
DEBUG(9, true);
partial_solutions.emplace_back(str, position + 2);
str[position] = current = opposite(lookbehind1);
str[position+1] = lookahead1 = '?';
DEBUG(9);
continue;
}
}
throw std::invalid_argument(str);
}
solutions.push_back(str);
no_solution:;
}
return solutions;
}
void run_test(
Solver &solver,
std::string const &test
)
{
std::cout << test << " -> ";
std::list<std::string> solutions = solver.solve(test);
int size = solutions.size();
for (const auto& solution : solutions)
{
std::cout << solution;
if (--size != 0)
{
std::cout << ", ";
}
}
std::cout << "\n";
}
int main()
{
std::list<std::string> tests = {
"?",
"??",
"???",
"a?",
"a??",
"a???",
"b?",
"b??",
"b???",
"a?a",
"a?b",
"b?a",
"b?b",
"a??a",
"a??b",
"b??a",
"b??b",
"aa?",
"ba?",
"a?bb",
"?bb?",
"?a",
"?aa",
"??aa",
"???aa",
"????aa",
"?ab",
"??ab",
"???ab",
"????ab",
"a?b?aa",
"ab???bb?",
"aa?bb",
"a?b?a?bb",
"?a?b?aa",
};
Solver solver = Solver();
for (const auto& test : tests)
{
run_test(solver, test);
}
}
def is_valid(s):
if not s:
return True
char = "x"
count = 0
for c in s:
if c != char:
char, count = c, 1
else:
count += 1
if count == 3:
return False
return True
# My greedy solution
def f(s):
if len(s) == 2:
return s.replace('?', 'a')
aa = ['a', 'a']
bb = ['b', 'b']
out = []
i = 0
a, b = 0, 0
while i < len(s):
if s[i] == 'a' or (s[i] == '?' and b == 2):
if s[i] == 'a' and a == 2:
if s[i-3:i-1] == "??":
out[i-3], out[i-2] = out[i-2], out[i-3]
a -= 1
else:
return ""
out.append('a')
a, b = a + 1, 0
i += 1
elif s[i] == 'b' or (s[i] == '?' and a == 2):
if s[i] == 'b' and b == 2:
if s[i-3:i-1] == "??":
out[i-3], out[i-2] = out[i-2], out[i-3]
b -= 1
else:
return ""
out.append('b')
a, b = 0, b + 1
i += 1
elif i == len(s) - 1:
out.append('a' if b else 'b')
i += 1
elif i == len(s) - 2:
if s[i+1] == '?':
out.extend(aa if b else bb)
else:
out.append('a' if b else 'b')
out.append(s[i+1])
i += 2
elif s[i+1] == '?':
if a:
out.append('a')
a, b = a + 1, 0
else:
out.append('b')
a, b = 0, b + 1
i += 1
elif s[i+1] == 'a':
if a or b < 2:
out.append('b')
a, b = 0, b + 1
else:
out.append('a')
a, b = a + 1, 0
i += 1
elif s[i+1] == 'b':
if b or a < 2:
out.append('a')
a, b = a + 1, 0
else:
out.append('b')
a, b = 0, b + 1
i += 1
return ''.join(out)
# https://dev59.com/4lEG5IYBdhLWcg3wQoNw#69322213
# Code by MTO
def solve(_str):
opposite = {"a": "b", "b": "a"}
curr_idx = 0
output = []
lookahead = lambda x: None if ((curr_idx + x < 0) or (curr_idx + x >= len(_str))) else _str[curr_idx + x]
lookbehind = lambda x: None if curr_idx-x< 0 else output[curr_idx - x]
matches = lambda x, y: x == y or x == None or y == None
is_replacement = lambda x: x == '?'
while curr_idx < len(_str):
curr = lookbehind(1) or 'b'
i = 0
next = lookahead(i)
while is_replacement(next):
i += 1
next = lookahead(i)
if next == None:
# Found the end of the string.
# Append characters opposite to the previous for each ?
for _ in range(i, 0, -1):
curr = opposite[curr]
output.append( curr )
break
if (i > 1):
# Found multiple successive ?s
# Handle the first half of the ?s by
# Append alternating characters from the previous character.
j = 0
while j < i / 2:
curr = opposite[curr]
output.append( curr )
j += 1
# Then handle the second half of the ?s
# append alternating characters to the next character after the ?s.
while j < i:
output.append( next if (j%2) == (i%2) else opposite[next] )
j += 1
elif i == 1:
# Found a single ?
prev = lookbehind(2)
if curr == prev and curr == opposite[next] and next == lookahead(2):
# No solution.
return None
if curr == prev or matches(curr, next):
output.append( opposite[curr] )
else:
output.append( curr )
if next != None:
# Output the next non-? character.
output.append( next )
curr_idx += i + 1
return ''.join(output)
strs = [
"a?bb", # "aabb"
"??abb", # "ababb" or "bbabb" or "baabb"
"a?b?aa", # "aabbaa"
"?bb?",
"aa?bb", # NO SOLUTION
"aa??aa", # "aabbaa"
"ab???bb?",
"????",
"??",
"?????",
"??????",
"?",
"a?",
"a??",
"a???",
"b?",
"b??",
"b???",
"a?a",
"a?b",
"b?a",
"b?b",
"a??a",
"a??b",
"b??a",
"b??b",
"aa?",
"ba?",
"a?bb",
"?bb?",
"??abb",
"a?b?aa",
"ab???bb?",
"aa?bb"
]
for s in strs:
_solve = solve(s)
_f = f(s)
print("%s\n%s, %s, %s, %s\n" % (s, is_valid(_f), is_valid(_solve), _solve, _f))
import random
def get_random(n):
char = 'x'
count = 0
out = []
not_c = lambda c: 'a' if c == 'b' else 'b'
for _ in range(n):
c = ['a', 'b'][int(random.random() * 2)]
if c != char:
out.append(c)
char, count = c, 1
elif count == 2:
out.append(not_c(c))
char, count = not_c(c), 1
else:
out.append(c)
count += 1
for i in range(n):
if int(random.random() * 2):
out[i] = '?'
return ''.join(out)
num_tests = 1000
n = 20
print("Starting random tests...")
for _ in range(num_tests):
s = get_random(n)
_solve = solve(s)
_f = f(s)
valid_solve = is_valid(_solve)
valid_f = is_valid(_f)
if not valid_f or not valid_solve:
print(s, valid_f, valid_solve, _f, _solve)
break
print("Done testing")
Python解决方案和测试函数：
import re
import random
def char_reverse(c: str) -> str:
if c=="a":
return "b"
return "a"
def contiguous(chars: str,i: int,**kwargs) -> str:
route = kwargs.get("route")
if i<1 and route=="left":
return "yy"
try:
if route=="left":
if i-2>=0:
return str(chars[i-2])+str(chars[i-1])
else:
if i-1==0:
return str(chars[i-1])
else:
return "yy"
if route=="right":
if i+1<len(chars)-1:
return str(chars[i+1])+str(chars[i+2])
else:
return str(chars[i+1])
except:
return "yy"
def char_check(chars: list, i: int) -> str:
left = contiguous(chars,i,route="left")
right = contiguous(chars,i,route="right")
#print(left[-1],right[0])
if left[-1]==right[0]:
return char_reverse(right[0])
if left=="aa" and right=="bb": #aa?bb => X, undefined
return "X"
if left=="bb" and right=="aa": #bb?aa => X, undefined
return "X"
if left=="ba" and right=="ab":
return "b"
if left=="ab" and right=="ba":
return "a"
if left=="aa":
return "b"
if left=="bb":
return "a"
if right=="aa":
return "b"
if right=="bb":
return "a"
return "a"
def main(string: str) -> str:
regex = r"\?"
match = re.finditer(regex, string)
indices = [m.start(0) for m in match]
list_str = list(string)
for i in indices:
list_str[i] = char_check(list_str,i)
new_str = "".join(list_str)
print("old_str",string)
print("new_str",new_str)
return new_str
### TEST ###
def test(string: str) -> str:
if "aaa" in string:
return False
if "bbb" in string:
return False
if "X" in string:
match = re.finditer(r"X", string)
indices = [m.start(0) for m in match]
for ti in indices:
left = contiguous(string,ti,route="left")
right = contiguous(string,ti,route="right")
print(left,right)
if left!="aa" and left!="bb":
return False
if right!="aa" and right!="bb":
return False
return True
def test_create_rand_string() -> str:
TEST_MAX_LENGTH = 150 # up to ∞
TEST_MIN_LENGTH = 1
string = ""
p_char = ""
char_list = ["a","b","?"]
for r in range(random.randint(TEST_MIN_LENGTH,TEST_MAX_LENGTH)):
c = random.choice(char_list)
if len(string)>1:
p_char = string[-1]
if c!=p_char or c=="?":
string += c
return string
for i in range(10000):
string = test_create_rand_string()
result = test(main(string))
if result==False:
print("error")
quit()
print("Test: %i" % i,result)
### TEST ###