5507. 替换所有的问号 [easy]
5507. 替换所有的问号 [easy]
给你一个仅包含小写英文字母和 '?' 字符的字符串 s ，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
注意：你 不能 修改非 '?' 字符。
题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：
输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2：
输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
示例 3：
输入：s = "j?qg??b"
输出："jaqgacb"
示例 4：
输入：s = "??yw?ipkj?"
输出："acywaipkja"
提示：
1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符
First Try
2020-09-06
周赛题目，一开始就看错题意了，以为整个字符串中不允许出现重复的字符，只到测试集出现一个100个问号的字符串，才知道是相邻字符不允许重复。
然后做的时候还以为要用上backtrack，也是写得一塌糊涂。其实只要求相邻字符不重复，不需要考虑字符串分配不够用的问题。毕竟只跟前和后对比，有3个字符都够了。
所以其实这道题真的是easy级别，只要选择与前后不同的字符直接往里扔就行了。需要稍微注意的，无非就是第一个字符和最后一个字符需要多加判断一下。
class Solution:
def modifyString(self, s: str) -> str:
col = set(s)
choices = list()
for i in range(26):
choices.append(chr(ord('a') + i))
rv = list(s)
for idx, c in enumerate(rv):
if c == "?":
pre_after = ["", ""]
if len(rv) == 1:
pre_after = ["", ""]
elif idx == 0 and len(rv) != 1:
pre_after[1] = rv[idx + 1]
elif idx == len(rv) - 1 and len(rv) != 1:
pre_after[0] = rv[idx - 1]
else:
pre_after = [rv[idx - 1], rv[idx + 1]]
for letter in choices:
if letter not in pre_after:
rv[idx] = letter
break
return ''.join(rv)
Failed Try
2020-09-06
以为是整个字符串中不允许出现重复的，所以用了backtrack暴力遍历算法分配字符。 当然由于理解错题意，直接超时挂掉了。
class Solution:
def modifyString(self, s: str) -> str:
col = set(s)
choices = set()
for i in range(26):
if chr(ord('a') + i) not in col:
choices.add(chr(ord('a') + i))
rv = list(s)
def backtrack(rv):
if "?" not in rv:
return True
elif not len(choices):
return False
for idx, c in enumerate(rv):
if c == '?':
for letter in list(choices):
rv[idx] = letter
choices.remove(letter)
if backtrack(rv):
return True
choices.add(letter)
rv[idx] = '?'
break
backtrack(rv)
return ''.join(rv)