如何在C语言中查找与用户输入最接近的字符串？

嘿，要实现你想要的“找不到输入时提示最接近字符串”的功能，核心是计算两个字符串的编辑距离（Levenshtein距离）——简单来说，就是把一个字符串转换成另一个所需的最少单字符编辑操作（插入、删除、替换）次数，次数越少说明两个字符串越相似。

下面我会基于你现有的代码，给出完整的实现方案：

第一步：先实现编辑距离的计算函数 #

这是核心逻辑，用动态规划来实现标准的Levenshtein距离计算：

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

// 计算两个字符串的Levenshtein编辑距离
int levenshteinDistance(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    // 创建动态规划表
    int **dp = (int **)malloc((len1 + 1) * sizeof(int *));
    
    for (int i = 0; i <= len1; i++) {
        dp[i] = (int *)malloc((len2 + 1) * sizeof(int));
        dp[i][0] = i; // 其中一个字符串为空时，距离等于另一个的长度
    }
    
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    
    // 填充动态规划表
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            // 当前字符相同则成本为0，不同为1
            int cost = (s1[i-1] == s2[j-1]) ? 0 : 1;
            // 取替换、删除、插入三种操作中的最小值
            dp[i][j] = dp[i-1][j-1] + cost;
            if (dp[i][j] > dp[i-1][j] + 1) {
                dp[i][j] = dp[i-1][j] + 1;
            }
            if (dp[i][j] > dp[i][j-1] + 1) {
                dp[i][j] = dp[i][j-1] + 1;
            }
        }
    }
    
    int distance = dp[len1][len2];
    
    // 记得释放申请的内存，避免内存泄漏
    for (int i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return distance;
}

第二步：修改你的主函数，加入查找最接近字符串的逻辑 #

我在你原来的代码基础上，添加了计算每个预设字符串与输入的编辑距离，找到距离最小的那个字符串：

int main(int argc, char* argv[]){ 
    char book[5][100] = {"donusum" , "korluk" , "satranc" }; 
    int bookCount = 3; // 这里注意你定义了5个位置，但只初始化了3个，所以用实际数量
    char input[100]; 
    printf("Enter a book name: "); 
    fgets(input, 100, stdin); 
    
    // 处理fgets带来的换行符，同时避免输入为空时越界
    if (strlen(input) > 0 && input[strlen(input)-1] == '\n') {
        input[strlen(input)-1] = 0; 
    }
    
    // 把输入转成小写，保持匹配的一致性
    for(int i=0; i< strlen(input); i++){ 
        input[i] = tolower(input[i]); 
    } 
    
    // 先检查输入是否和预设字符串完全匹配
    int foundIndex = -1;
    for(int i=0; i<bookCount; i++){ 
        if(strcmp(book[i], input)==0){ 
            printf("Found input string at book list.\n"); 
            foundIndex = i;
            break; 
        } 
    } 
    
    // 如果没找到，就找最接近的
    if(foundIndex == -1){ 
        printf("The input string was not found.\n");
        int minDistance = -1;
        int closestIndex = 0;
        // 遍历所有预设字符串，计算距离并记录最小的那个
        for(int i=0; i<bookCount; i++){
            int distance = levenshteinDistance(input, book[i]);
            if(minDistance == -1 || distance < minDistance){
                minDistance = distance;
                closestIndex = i;
            }
        }
        printf("你是不是指这个？%s\n", book[closestIndex]);
    } 
    return 0;
}

一些额外的小提示 #

• 这个方法对于少量预设字符串（比如你这里的3个）非常高效，如果以后预设字符串数量很多，可以考虑优化（比如先按长度过滤，减少需要计算的字符串数量）。
• 如果有多个字符串和输入的距离相同，当前代码会返回第一个遇到的最接近字符串，你可以根据需求修改，比如把所有最接近的都列出来。
• 处理输入换行符的时候加了判断，避免用户直接按回车导致的数组越界问题。

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