解题思路与方法

算法概述

本题要求在大量已知子命令中，根据用户输入的错误命令，找到与之最相似（即编辑距离最小）的子命令并提示。 最相似的定义为Levenshtein 距离，即将一个字符串通过 替换、插入、删除 三种基本操作变为另一个字符串所需的最少步数。

详细方法

1. 逐一计算编辑距离

   • 对用户输入串 s 和每个候选子命令 t，使用动态规划求它们的编辑距离 d(s,t)。

   • 定义 dp[i][j] 表示 s[0..i) 转换成 t[0..j) 的最少操作数。

   • 初始条件：

     • dp[0][j]=j（s 为空，插入 j 个字符），
     • dp[i][0]=i（删除 i 个字符）。

   • 转移方程：

     if s[i-1]==t[j-1]:
       dp[i][j]=dp[i-1][j-1]
     else:
       dp[i][j]=min(
         dp[i-1][j]+1,   // 删除 s[i-1]
         dp[i][j-1]+1,   // 插入 t[j-1]
         dp[i-1][j-1]+1  // 替换为 t[j-1]
       )
     

2. 查找最小距离或候选集

   • 遍历所有子命令，若距离 =0，说明恰好匹配，直接输出该命令并结束。
   • 否则，收集所有满足 1≤d(s,t)≤D 的命令，记录距离。

3. 排序与输出

   • 按距离从小到大排序，相同距离下按字典序升序排列。
   • 若候选集非空，依次输出；否则输出 None。

复杂度分析

• 每次编辑距离计算的时间为 $O(|s|\times|t|)$，最坏长度均为 $L$，则为 $O(L^2)$。

• 总共 $N$ 个子命令，时间复杂度为 $O(N\times L^2)$。

  • 在本题中 $N\le3\times10^4,;L\le25$，$N L^2\approx1.9\times10^7$，在常数较小的实现下可接受。

• 空间复杂度若使用全表为 $O(L^2)$，也可优化为 $O(L)$ 的滚动数组。

代码实现

Python

def edit_dist(a, b):
    n, m = len(a), len(b)
    dp = [list(range(m+1))] + [[i]+[0]*m for i in range(1, n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # 删除
                    dp[i][j-1] + 1,    # 插入
                    dp[i-1][j-1] + 1   # 替换
                )
    return dp[n][m]

def main():
    D = int(input().strip())
    N = int(input().strip())
    cmds = [input().strip() for _ in range(N)]
    inp = input().strip()

    # 精确匹配
    if inp in cmds:
        print(inp)
        return

    # 计算距离并筛选
    cand = []
    for cmd in cmds:
        d = edit_dist(inp, cmd)
        if 1 <= d <= D:
            cand.append((d, cmd))

    # 输出结果
    if not cand:
        print("None")
    else:
        cand.sort(key=lambda x: (x[0], x[1]))
        print(" ".join(cmd for _, cmd in cand))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    // 计算编辑距离
    static int dist(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i-1) == b.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1),
                        dp[i-1][j-1] + 1
                    );
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        int N = sc.nextInt();
        List<String> cmds = new ArrayList<>();
        for (int i = 0; i < N; i++) cmds.add(sc.next());
        String inp = sc.next();

        // 精确匹配
        if (cmds.contains(inp)) {
            System.out.println(inp);
            return;
        }

        // 筛选候选
        List<int[]> cand = new ArrayList<>();
        for (String cmd : cmds) {
            int d = dist(inp, cmd);
            if (d >= 1 && d <= D) {
                cand.add(new int[]{d, cmds.indexOf(cmd)});
            }
        }

        if (cand.isEmpty()) {
            System.out.println("None");
        } else {
            // 排序
            cand.sort((a, b) -> {
                int da = a[0], db = b[0];
                if (da != db) return da - db;
                return cmds.get(a[1]).compareTo(cmds.get(b[1]));
            });
            // 输出
            StringJoiner sj = new StringJoiner(" ");
            for (int[] p : cand) sj.add(cmds.get(p[1]));
            System.out.println(sj.toString());
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算编辑距离
int editDist(const string &a, const string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1});
        }
    }
    return dp[n][m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int D, N;
    cin >> D >> N;
    vector<string> cmds(N);
    for (int i = 0; i < N; i++) cin >> cmds[i];
    string inp;
    cin >> inp;

    // 精确匹配
    for (auto &cmd : cmds) {
        if (cmd == inp) {
            cout << inp << "\n";
            return 0;
        }
    }

    // 筛选候选
    vector<pair<int,string>> cand;
    for (auto &cmd : cmds) {
        int d = editDist(inp, cmd);
        if (d >= 1 && d <= D) {
            cand.emplace_back(d, cmd);
        }
    }

    if (cand.empty()) {
        cout << "None\n";
    } else {
        sort(cand.begin(), cand.end(), [](auto &a, auto &b) {
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second;
        });
        bool first = true;
        for (auto &p : cand) {
            if (!first) cout << ' ';
            cout << p.second;
            first = false;
        }
        cout << '\n';
    }
    return 0;
}

题目内容

在使用命令行工具时，经常会出现手工输入错字母的情况，如想要输入:

git clone

输入成了

git clane

因此为了命令行工具更易用，需要从支持的子命令列表中找到最相似的子命令提示给用户。

最相似的定义为最短莱文斯坦距离:即两个字符串之间，由一个转成另一个所需的最少编辑操作次数。

允许的编辑操作包括:

1.将一个字符替换成另一个字符

2.插入一个字符

3.删除一个字符

输入描述

第一行给出可提示的最短距离$D$，第二行给出子命令数量$N$，后面N行给出所有的子命令 列表，最后一行给出用户输入的子命令。

$1<=D<=5$

$1<=N<=30000$

单个子命令长度$2<=L<=25$，子命令只包含小写字母

输出描述

输出为分三种情况:

1.用户输入的子命令正确匹配上某个子命令参数，输出原命令。

2.用户输入的子命令没有匹配上某个子命令参数，但是符合提示要求，则输出提示命令，如$clone$;如果符合提示要求的子命令有多个，则按距离从小到大排序后输出，同一个距离内还有多个的按字母序从小到大输出。

3.用户输入的子命令没有匹配上某个子命令参数，且没有符合提示要求的子命令，则输出$None$

样例1

输入

2
3
clone
checkout
switch
clane

输出

clone 

说明

第一行值为2，表示当前输入不能完全正确匹配某个子命令时，则将其最短距离小于2的子命令作为提示输出

第二行为3，表示命令行实际有3个子命令，分别为后续3行

最后一行为用户实际的输入

由于用户没有命中具体的子命令，而clone与用户输入的距离为1，满足小于2的要 求，因此输出clone

样例2

输入

2
3
clone
checkout
switch
create

输出

None

说明

输入的三个子命令中没有满足与$create$距离小于等于$2$的，因此输出$None$

样例3

输入

2
5
aprint
bprint
aaprint
bbprint
output
print

输出

aprint bprint aaprint bbprint

说明

子命令中有四个满足与$print$的距离小于等于$2$，其中$aprint$与$bprint$与目标的距离为$1$，先将其排序并输出，$aaprint\ bbprint$与目标的距离为$2$，排序后接在前面输出后继续输出