题目的主要信息：

6条配置命令如下：
匹配原则如下：
- 若只输入一字串，则只匹配一个关键字的命令行，采用最短唯一匹配，输入命令不一定要完整
- 若只输入一字串，但本条命令有两个关键字，则匹配失败
- 若输入两字串，则先匹配第一关键字，如果有匹配但不唯一，继续匹配第二关键字，如果仍不唯一，匹配失败
- 若输入两字串，则先匹配第一关键字，如果有匹配但不唯一，继续匹配第二关键字，如果唯一，匹配成功
- 若输入两字串，第一关键字匹配成功，则匹配第二关键字，若无匹配，失败
- 若匹配失败，打印“unknown command”
进阶要求：时间复杂度 $O (n)$ ，空间复杂度 $O (n)$

方法一：遍历匹配

具体做法：

我们可以将完整的命令与输出的执行组成一个map，存在TreeMap中。

然后将输入的命令根据空格分割成多条，再依次与map中的命令匹配。遍历map，将完整的配置命令也分割成多条，如果条数与输入的命令相同才有匹配的可能性，然后遍历每一个子串依次比较，子串中的每个字符（因为不完全匹配，因此只要匹配的时候输入命令子串全部被匹配了即可），如果每个子串都匹配则认为这个命令是匹配了，获取value值，统计本次匹配的命令个数。

最后只输出匹配个数为1的value值，其他情况要么没有匹配要么重复匹配，都是“unknown command”。

alt

import java.util.*;
import java.util.regex.*;

public class Main {
    public static boolean ismatch(String s1, String s2){ //匹配两个子串
        char[] a = s1.toCharArray(); //转成字符数组
        char[] b = s2.toCharArray();
        int i = 0;
        while(i < s1.length() && i < s2.length()){  //遍历比较字符
            if(a[i] == b[i])
                i++;
            else
                break;
        } 
        if(i == s1.length()) //只把输入命令匹配完整
            return true;
        else
            return false;
    }
    
    public static void main(String[] args){
        TreeMap<String, String> map = new TreeMap<String, String>(); //连接命令和操作字符为map
        map.put("reset", "reset what");
        map.put("reset board", "board fault");
        map.put("board add", "where to add");
        map.put("board delete", "no board at all");
        map.put("reboot backplane", "impossible");
        map.put("backplane abort", "install first");
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            String cmd = scan.nextLine().trim();
            String[] cmds = cmd.split(" ");//按空格分割
            int count = 0; //记录匹配的命令个数
            String output = "";
            for(Map.Entry<String, String> c : map.entrySet()){  //遍历命令集合
                String[] temp = c.getKey().split(" "); //配置命令分割
                if(temp.length == cmds.length){ //子串数相同才能匹配
                    int i = 0;
                    while(i < cmds.length){ 
                        if(ismatch(cmds[i], temp[i])) //匹配每一个子串
                            i++;
                        else
                            break;
                    }
                    if(i == cmds.length){ //所有子串都匹配
                        output = c.getValue();
                        count++; //匹配数+1
                    }
                }
            }
            if(count != 1) //不唯一匹配或者没有匹配
                System.out.println("unknown command");
            else
                System.out.println(output);
        }
    }
}

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为输入的条数，对于每条命令，遍历map只需要6次，最多2个子串，每个子串匹配遍历次数也不会超过9次，因此每条命令的匹配都是常数时间
空间复杂度： $O (1)$ ，常数空间

方法二：正则表达式

具体做法：

因为输入的命令是可能缺省的，我们可以以空格分割子串后用正则表达式将每个输入命令的子串都补齐，补齐后再连接成长字符串，然后依次与map中的命令做正则匹配，输出仅匹配成功1次的结果，其余都是“unknown command”。

import java.util.*;
import java.util.regex.*;

public class Main {
    public static void main(String[] args){
        TreeMap<String, String> map = new TreeMap<String, String>(); //连接命令和操作字符为map
        map.put("reset", "reset what");
        map.put("reset board", "board fault");
        map.put("board add", "where to add");
        map.put("board delete", "no board at all");
        map.put("reboot backplane", "impossible");
        map.put("backplane abort", "install first");
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            String cmd = scan.nextLine().trim();
            String[] cmds = cmd.split("\\ +");//按空格分割
            String pattern = "";
            for(int i = 0; i < cmds.length - 1; i++)
                pattern = pattern.concat(cmds[i] + "[a-z]*\\ +");//匹配关键字和空格
            pattern = pattern.concat(cmds[cmds.length - 1] + "[a-z]*");//匹配关键字，不带空格
            String output = "unknown command";     
            boolean flag = true;//记录是否匹配到多个
            for(Map.Entry<String, String> c : map.entrySet()){  //遍历命令集合
                if(c.getKey().matches(pattern)){ //正则比较集合中的key值和正则字符串
                    if(flag){
                        output = c.getValue();
                        flag = false; //记录已经匹配到了
                    } else {
                        output = "unknown command";
                        break;//匹配到多个，跳出循环
                    } 
                }
            }
            System.out.println(output);
        }
    }
}

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为输入的条数，对于每条命令，遍历map只需要6次，最多2个子串，因此每条命令的处理和匹配时间都是常数时间
空间复杂度： $O (1)$ ，常数空间

题解 | #配置文件恢复#

题目的主要信息：

方法一：遍历匹配

方法二：正则表达式