题解 | #牛群密码 - 有效回文#

考察知识点: 回文字符串，遍历

解题思路：

1、首先遍历数组，判断字符串是否至多有 k 个不同的字符；

2、在满足条件1的情况下去判断遍历去除一个字符形成新字符串是否是回文的可能性；

详细解析在代码注释中显示。

采用的编程语言：C

完整的编码程序：如下所示

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param password string字符串 
 * @param k int整型 
 * @return bool布尔型
 */
#include <stdbool.h>
#include <string.h>
bool isValidPalindrome(char* password, int k ) {
    char char_list[26] = {0};
    int same_char_flag = 0;
    int char_count = 0;

    char tmp_passwd[2 * 10000 * 100] = {0};
    int tmp_count = 0;
    int flag = 0;

  	/* 遍历出所有不相同的字符，并保存到char_list */
    for (int i = 0; i < strlen(password); i++) {
        for (int j = 0; j < 26; j++) {
		  /* 在已经保存的字符串中发现了相同的字符 */
            if (password[i] == char_list[j]) {
                same_char_flag = 1;
                break;
            }
        }

	  /* 如果没有在保存的字符串中发现相同的字符，就将该字符保存到char_list，并做统计 */
        if (same_char_flag == 0) {
            char_list[char_count] = password[i];
            char_count++;
        }
    }

  /* 统计到的不相同的字符比传入的k值要大时，就结束程序 */
    if (char_count > k) {
        printf("cahr count:%d", char_count);
        return false;
    }

  /* 遍历去除一个字符形成新字符串的所有可能 */
    for (int i = 0; i < strlen(password); i++) {
        tmp_count = 0;
        flag = 0;
	  /* 将去除对应字符后形成的字符串保存到 tmp_passwd*/
        for (int j = 0; j < strlen(password); j++) {
            if (j != i)
                tmp_passwd[tmp_count++] = password[j];
        }

	  /* 对新的字符串做回文字符串判断 */
        for (int j = 0; j < ((strlen(password) - 1) / 2); j++) {
            if (tmp_passwd[j] != tmp_passwd[(strlen(password) - 2) -j]) {
                flag = 1;
                break;
            }
        }

	  /* 如果所有字符都相同的情况下，该flag会保持为0 */
        if (flag == 0)
            break;
    }

    if (flag)
        return false;
    else
        return true;
}