最少插入以形成回文并允许排列  


难度级别 中等
经常问 亚马逊 编码国家 指令 谷歌 的确 意会
动态编程

问题“最小插入以形成允许排列的回文集”指出给您一个字符串,所有字母均小写。 问题陈述要求找出字符在字符串中的最少插入量,以使其可以成为回文。 字符的位置可以在字符串中更改。

使用案列  

最少插入以形成回文并允许排列

malyalam
1

说明

如果我们可以在初始字符串中添加“ a”,则可以创建回文。

madaam
1

说明

添加'd'或'a'组成原始字符串回文。

算法  

  1. 将字符串的长度设置为 l 并输出为0。
  2. 声明 整数 排列.
  3. 存储并维护字符串中每个字符的计数。
  4. 从0开始遍历数组,而i <26。
    1. 检查是否 countChar [i] %2 == 1
      1. 如果为true,则执行output ++。
  5. 如果输出等于0,则返回0。
  6. 否则返回输出1。

说明

给你一个 绳子,您的任务是找出要在字符串中完成的最小插入量,以使其成为回文。 字符的位置可以在字符串中更改。 我们将计算字符串字符的出现并将其存储到数组中。 因为背后的想法是,当字符串是回文字符串时,当字符串长度为奇数时,只有一个字符可以为奇数。 除此之外,所有字符的频率都是偶数。 因此,我们需要找到出现奇数次的字符。

参见
石头游戏II Leetcode

我们将计算输入字符串中的每个字符并将其存储到数组中。 正如我们已经提到的,回文字符串只能具有一个出现奇数次的字符。 因此输出将比字符数少一。 将每个出现的字符串存储在数组中之后。 然后,我们使数组从i = 0遍历到i小于26。这是因为总共有26个字符,并且应该假定在给定的字符串中有26个字符出现的可能性。

在遍历数组时,我们将检查是否将每个计数除以2,如果剩余为1,则为true,那么它将使输出计数增加1(output ++)。 遍历一个数组后,如果count保持为零,则意味着我们在字符中什么都找不到,这是奇数意味着该字符串已经是回文,我们将返回0,否则将返回(output-1),因为我们已经提到过输出将小于字符数,因此我们得到了输出。

代码  

C ++代码查找允许插入以形成回文的最小插入

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

Java代码查找允许插入的最小插入以形成回文

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是输入字符串中的字符数。

参见
查找流中的前K个(或最常见)数字

空间复杂度

O(1), 因为我们创建了一个具有恒定大小的额外数组。 因此,空间复杂度是恒定的。