C语言计算字符串转为另一字符串排列所需操作次数问题

你的代码核心问题是替换次数的计算逻辑完全错误，其次存在输入未加字符串结束符的潜在风险，具体问题和修复方案如下： #

存在的Bug #

• 替换次数统计错误：原代码只要字符计数不等就给替换次数+1，统计的是有差异的字符种类数，不是实际需要的替换操作数。比如aab和abb，原代码会算替换次数2（a和b的计数都不等），实际只需要替换1次。
• 输入处理缺失字符串结束符：输入的str1、str2末尾没有添加\0，如果后续需要调用字符串处理函数会直接出错。

正确计算逻辑 #

我们的目标是把str2修改为str1的大小写不敏感、空格不敏感排列，且替换操作优先级最高，计算逻辑如下：

1. 预处理阶段忽略空格、统一转小写，统计两个字符串的有效字符长度和各字符出现次数
2. 计算公共匹配字符数：遍历所有ASCII字符，对每个字符取两个计数的最小值累加，得到不需要修改的字符总数
3. 替换次数计算：str1缺失的总字符数是len1 - 公共匹配数，str2多余的总字符数是len2 - 公共匹配数，两者的最小值就是最多可以用替换解决的数量，也就是实际需要的替换次数
4. 增删次数计算：如果str2有效长度比str1小，需要新增的次数是len1 - len2；如果更大，需要删除的次数是len2 - len1

修复后代码 #

#include <stdio.h>
#define LENGTH 100

int main()
{
    char str1[LENGTH] = {0};
    char str2[LENGTH] = {0};
    int cnt1[128] = {0};
    int cnt2[128] = {0};
    char c = 0;
    int len1 = 0, len2 = 0;
    int add = 0, del = 0, replace = 0;
    int common = 0;
    int i;

    printf("请输入乱序句子：\n");
    for(len1 = 0; len1 < LENGTH-1 && (c = getchar()) != EOF && c != '\n'; len1++) {
        if(c >= 'A' && c <= 'Z')
            str1[len1] = c + 32;
        else if(c == ' ')
            len1--;
        else
            str1[len1] = c;
    }
    str1[len1] = '\0'; // 补字符串结束符

    printf("请输入目标句子：\n");
    for(len2 = 0; len2 < LENGTH-1 && (c = getchar()) != EOF && c != '\n'; len2++) {
        if(c >= 'A' && c <= 'Z')
            str2[len2] = c + 32;
        else if(c == ' ')
            len2--;
        else
            str2[len2] = c;
    }
    str2[len2] = '\0'; // 补字符串结束符

    // 统计字符计数
    for(i = 0; i < len1; i++) cnt1[str1[i]]++;
    for(i = 0; i < len2; i++) cnt2[str2[i]]++;

    // 计算公共匹配字符数
    for(i = 0; i < 128; i++) {
        common += (cnt1[i] < cnt2[i] ? cnt1[i] : cnt2[i]);
    }

    // 计算三种操作次数
    replace = (len1 - common) < (len2 - common) ? (len1 - common) : (len2 - common);
    if(len2 < len1) add = len1 - len2;
    else if(len2 > len1) del = len2 - len1;

    // 输出结果
    if(add == 0 && del == 0 && replace == 0) {
        printf("str2是str1的大小写、空格不敏感排列");
    } else {
        printf("str2不是str1的大小写、空格不敏感排列，需要对str2做以下修改：\n");
        if(replace > 0) printf("替换%d个字符\n", replace);
        if(add > 0) printf("新增%d个字符\n", add);
        if(del > 0) printf("删除%d个字符\n", del);
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Josef Sigron