查找给定字符串按字典顺序最小的回文

Question

我需要找到按字典顺序最小的回文。例如，

s = "axxb??"

两个问号可以分别替换为字符

a

和

b

，组成字符串

s ="axbab" 

并且可以通过插入字符串将字符串重新排列为

"abxxba"

，这是字典上可能的最小回文。

它有效

string='a?rt???' 

并给我输出为

'aartraa'

。这里的问号可以用

'a','r','a' and 'a'

代替，组成回文。但当我尝试另一个

string='ai?a??u'

我得到“回文不可能”。下面是我尝试过的代码。

def find_smallest_palindrome(s):
    s = list(s)
    n = len(s)
    i, j = 0, n - 1

    while i < j:
        if s[i] == "?" and s[j] == "?":
            s[i] = "a"
            s[j] = "a"
        elif s[i] == "?":
            s[i] = s[j]
        elif s[j] == "?":
            s[j] = s[i]
        elif s[i] != s[j]:
            return "Palindrome not possible"

        i += 1
        j -= 1

    return "".join(s)


s = "ai?a??u"
candidate = find_smallest_palindrome(s)

if candidate == "Palindrome not possible":
    print("Palindrome not possible")
else:
    print(candidate)

Answer 1

我认为你错过了更大的图景。即：

• 如果 (a) 字符串的长度是偶数并且每个字母出现偶数次，或者 (b) 字符串的长度是奇数并且每个字母出现，则可以重新排列字符串的字母以形成回文除非有一个出现偶数次。

• 给定一个符合上述标准的字符串，可以从该字母组成的最小字谜词需要您按字母顺序取最小字母的一半（如有必要，向下舍入），然后按字母顺序取下一个最小字母的一半，...然后是中间出现一次奇数计数的字母 [如果总长度是奇数]，后面是所有内容的相反顺序。

所以

1. 计算每个字母的数量，并计算“？”的数量。

2. 如果总长度是偶数，请指定一个“？”对于每个具有奇数计数的字母。如果总长度是奇数，请分配一个“？”除字母顺序最大的字母外，每个具有奇数计数的字母。如果你没有足够的“？”，那么你就不走运，无法形成回文。

3. 您将剩下偶数个“？”（可能是 0 个）。让它们全部为“a”，或者任何最小的合法字母。

4. 如上所述形成回文。