如何降低基于Levenshtein距离的拼写检查器Main方法圈复杂度？

需求概述 #

• 实现简单拼写检查器，核心功能：
  • 用户输入错误句子/单词、数字N及N个正确单词
  • 输出规则：
    • 错误单词: 建议词（多个建议用空格分隔）
    • 无建议则输出「错误单词: no suggestions」
    • 所有单词正确则输出「Correct text!」
  • 支持处理四类拼写错误：拼写错误单词、字母交换、多余字母、缺失字母
• 已基于Levenshtein最小距离算法完成实现，测试用例全部通过，但Main方法圈复杂度为27，需降至26以下，寻求优化方案

示例输入 #

Thsi is an texzt fr tet
5
This 
an
text
for
test

示例输出 #

Thsi: This
an: no suggestions
texzt: text
fr: for
tet: text test

现有实现代码 #

using System;
using System.Collections.Generic;

namespace MisspelledWords
{
    class Program
    {
        static void Main(string[] args)
        {
            string sentence = Console.ReadLine();
            sentence = sentence.ToLower();
            int numWords = int.Parse(Console.ReadLine());
            const int doi = 2;
            const int doi2 = 3;
            int index = 0;
            int index1 = 0;
            string[] correctWords = new string[numWords];
            for (int i = 0; i < numWords; i++)
            {
                correctWords[i] = Console.ReadLine();
            }

            foreach (string word in sentence.Split(' '))
            {
                index++;
                int minDistance = int.MaxValue;
                string closestWord = "";
                foreach (string correctWord in correctWords)
                {
                    int distance = GetLevenshteinDistance(word, correctWord);
                    if (distance < minDistance)
                    {
                        minDistance = distance;
                        closestWord = correctWord;
                    }
                }

                Message(minDistance, closestWord, word, index, ref index1, correctWords);
                if (index1 != 0)
                {
                    return;
                }
            }

            static void Message(int minDistance, string closestWord, string word, int index, ref int index1, string[] correctWords)
            {
                if (minDistance >= doi)
                {
                    // Print the misspelled word followed by "no suggestions"
                    Console.WriteLine(word + ": (no suggestion)");
                }
                else if (minDistance < doi && closestWord != word || minDistance >= doi2)
                {
                    // Find all correct words that have the same minimum distance
                    List<string> suggestions = new List<string>();
                    foreach (string correctWord in correctWords)
                    {
                        int distance = GetLevenshteinDistance(word, correctWord);
                        if (distance == minDistance)
                        {
                            suggestions.Add(correctWord);
                        }
                    }

                    // Print the misspelled word followed by the suggestions
                    Console.Write(word + ": ");
                    Console.WriteLine(string.Join(" ", suggestions));
                }
                else if (minDistance == 0 && index > 1)
                {
                    Console.WriteLine("Text corect!");
                    index1++;
                }
            }

            static int Min(int value1, int value2, int value3)
            {
                return Math.Min(Math.Min(value1, value2), value3);
            }

            static int GetLevenshteinDistance(string word1, string word2)
            {
                int[,] distance = new int[word1.Length + 1, word2.Length + 1];

                InitializeDistanceMatrix(distance, word1, word2);
                CalculateLevenshteinDistance(distance, word1, word2);

                return distance[word1.Length, word2.Length];
            }

            static void InitializeDistanceMatrix(int[,] distance, string word1, string word2)
            {
                for (int i = 0; i <= word1.Length; i++)
                {
                    for (int j = 0; j <= word2.Length; j++)
                    {
                        if (i == 0)
                        {
                            distance[i, j] = j;
                        }
                        else if (j == 0)
                        {
                            distance[i, j] = i;
                        }
                    }
                }
            }

            static void CalculateLevenshteinDistance(int[,] distance, string word1, string word2)
            {
                for (int i = 0; i <= word1.Length; i++)
                {
                    for (int j = 0; j <= word2.Length; j++)
                    {
                        CLD(i, j, distance, word1, word2);
                    }
                }
            }

            static void CLD(int i, int j, int[,] distance, string word1, string word2)
            {
                const int v = 2;
                if (i <= 0 || j <= 0)
                {
                    return;
                }

                distance[i, j] = Min(
                    distance[i - 1, j] + 1,
                    distance[i, j - 1] + 1,
                    distance[i - 1, j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1));

                // Check if swapping the characters at positions i and j results in a new minimum distance
                if (i <= 1 || j <= 1 || word1[i - 1] != word2[j - v] || word1[i - v] != word2[j - 1])
                {
                    return;
                }

                distance[i, j] = Math.Min(distance[i, j], distance[i - v, j - v] + 1);
            }

            Console.ReadLine();
        }
    }
}

优化方案 #

1. 拆分Main方法，提取独立子逻辑 #

将Main中的输入读取、单词检查、结果输出等逻辑拆分为单独方法，减少Main方法内的分支与循环嵌套：

• 新增ReadInput方法负责读取句子、正确单词列表
• 新增CheckSingleWord方法处理单个单词的距离计算与建议生成

2. 修复并简化Message方法的条件判断 #

原Message方法中minDistance >= doi2分支永远不会触发（doi2=3>doi=2），直接删除该冗余分支；同时将全局正确判断移至所有单词检查完成后，避免中途终止程序的分支逻辑：

static void PrintResult(string word, int minDistance, List<string> suggestions)
{
    if (minDistance >= 2)
    {
        Console.WriteLine($"{word}: no suggestions");
    }
    else if (minDistance > 0)
    {
        Console.WriteLine($"{word}: {string.Join(" ", suggestions)}");
    }
}

3. 合并距离计算逻辑，避免重复遍历 #

原逻辑对单个单词两次遍历正确单词列表（一次找最小距离，一次收集同距离单词），合并为一次遍历，同时记录最小距离与建议列表：

static (int minDistance, List<string> suggestions) GetSuggestions(string word, string[] correctWords)
{
    int minDistance = int.MaxValue;
    List<string> suggestions = new List<string>();
    foreach (string correctWord in correctWords)
    {
        int distance = GetLevenshteinDistance(word, correctWord);
        if (distance < minDistance)
        {
            minDistance = distance;
            suggestions.Clear();
            suggestions.Add(correctWord);
        }
        else if (distance == minDistance)
        {
            suggestions.Add(correctWord);
        }
    }
    return (minDistance, suggestions);
}

4. 全局正确判断后置 #

遍历完所有单词后，统一判断是否所有单词的最小距离都是0，再输出「Correct text!」，移除原逻辑中index1这类控制程序终止的变量。

5. 清理冗余常量与变量 #

• 删除无实际作用的常量doi2
• 移除仅用于错误全局判断的index变量，替换为记录所有单词是否正确的布尔值

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