我有一个长度为 1 <= |S| <= 100 的字符串和 K (1 <= K <= 10)
这个字符串包含digits < K和问号。我想用 digits < K 替换这些问号，没有两个相邻的数字是相等的。该字符串是圆形的，所以它不能像这样:1?1或 11? .
结果字符串必须是字典序中最小的。
示例输入和输出
input:
K = 4
string = ?????
output:
01012
我尝试了一种贪婪的方法，但它对一些未知的测试用例失败了。我认为它需要一个 dp 方法但无法弄清楚状态，并且纯递归代码不适合时间。
对 dp 方法有什么帮助，或者贪心失败的棘手测试用例？
谢谢，
最佳答案
如果你在字符串的一端有一个数字，贪心算法会给你正确的答案。
如果您的字符串以问号开头和结尾，那么第一个字符有 2 种可能(0 或 1)，对这两种情况都运行贪心算法并取最好的。
Likao 指出的错误答案:
贪心法有效，但您必须从紧跟在已知数字之后的第一个问号开始。
关于algorithm - 动态规划方法或贪婪失败的案例，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10885541/