描述

题目描述

输入描述：

多行字符串，每行字符串一条命令

输出描述：

执行结果，每条命令输出一行

示例

输入：
reset
reset board
board add
board delet
reboot backplane
backplane abort
输出：
reset what
board fault
where to add
no board at all
impossible
install first

知识点：字符串，模拟，正则表达式

难度：⭐⭐⭐

题解

方法一：模拟

图解：

算法流程：

• 两个变量分别记录匹配成功的命令数量、匹配成功后在map的key
• 分输入命令的长度，分情况遍历每个命令进行前缀的匹配
• 匹配成功后更新两个变量
• 最后判断匹配成功的次数，结果为1才表示匹配上

Java 版本代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s=sc.nextLine();
            recover(s);
        }
    }
    public static void recover(String s){
        String[] strings = {"reset","reset board","board add","board delete","reboot backplane","backplane abort"};
        Map<String,String>map=new HashMap<>();
        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");
        String ERROR = "unknown command";
        String[] inputArr = s.split(" ");
        // 输入的命令长度为1
        if (inputArr.length==1){
            String input = inputArr[0];
            String cmd = strings[0].substring(0, input.length());
            if (cmd.equals(input)){
                System.out.println("reset what");
            }else {
                System.out.println(ERROR);
            }
        }else { 
        	// 匹配成功的命令数量
        	int count = 0;
            // 匹配成功后在map的key
            String key = "";
            // 穷举二字串的命令
            for (int i = 1 ; i < strings.length ; i++){
                String input1 = inputArr[0], input2 = inputArr[1];
                String command = strings[i];
                String[] cmd = command.split(" ");
                if (cmd.length==2){
                    String cmd1 = cmd[0], cmd2 = cmd[1];
                    // 输入的命令长度天长，不匹配该命令
                    if (cmd1.length() < input1.length() || cmd2.length() < input2.length()){
                        continue;
                    }
                    String s1 = cmd1.substring(0, input1.length());
                    String s2 = cmd2.substring(0, input2.length());
                    // 匹配前缀
                    if (s1.equals(input1) && s2.equals(input2)){
                    	// 匹配成功后的
                        key = command;
                        // 统计匹配成功的次数
                        count++;
                    }
                }
            }
            // 只能匹配成功一个
            if (count == 1){
                System.out.println(map.get(key));
            }else {
                System.out.println(ERROR);
            }
        }
    }

}

复杂度分析：

时间复杂度：$O(1)O(1)$, 每个输入最多需要进行5次处理判断

空间复杂度：$O(1)O(1)$, 只用到常数级别的空间

方法二：正则表达式匹配

解题思路：

借助正则表达式，对每个命令进行匹配

算法流程：

• 两个变量记录有多少match的指令、最后一个match的指令的下表
• 将输入的字符串与每个命令进行匹配
  • 在输入的字符串后面加上 “.*”，就可进行模糊匹配
• 最后根据匹配的次数是否为1，来获取结果

Java 版本代码如下：

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] commands = {"reset", "reset board", "board add", "board delete", 
                                 "reboot backplane", "backplane abort"};
        String[] responses = {"reset what", "board fault", "where to add", 
                                  "no board at all", "impossible", "install first", "unknown command" };
        while (in.hasNextLine()) { 
            String input = in.nextLine();
            if(input.isEmpty()){//阻止最后一行的空行输出unknown command
                continue;
            }
            int match_num = 0;//记录有多少match的指令
            int index = 6;//记录最后一个match的指令的下表
            for(int i=0;i<commands.length;i++){
                if(match(input, commands[i])){
                    match_num++;
                    index = i;
                }
            }
            if(match_num!=1){
                index = 6;
            }
            System.out.println(responses[index]);

        }
    }
	
	// 正则表达式匹配
    public static boolean match(String input, String command){
        if(input.isEmpty()){//空白输入不应该有符合的结果
            return false;
        }
        String[] inputs = input.split(" ");
        String[] commands = command.split(" ");
        if(inputs.length==1 && commands.length==1){
            String pattern = input+".*";
            return Pattern.matches(pattern, command);
        }else if(inputs.length==2 && commands.length==2){
            String pattern_1 = inputs[0]+".*";
            String pattern_2 = inputs[1]+".*";
            return Pattern.matches(pattern_1, commands[0]) && Pattern.matches(pattern_2, commands[1]);
        }
        return false;
    }
}

复杂度分析：

时间复杂度：$O(1)O(1)$, 每个输入最多需要进行5次处理判断

空间复杂度：$O(1)O(1)$, 只用到常数级别的空间