解题思路
这是一个命令匹配问题,需要按照"最短唯一匹配原则"处理输入命令。处理步骤:
- 首先定义所有合法命令和对应的输出结果
- 根据输入的字符串数量分类处理:
- 一个字符串:只匹配单关键字命令
- 两个字符串:需要依次匹配两个关键字
- 使用前缀匹配来判断命令
- 按照题目规则处理各种匹配情况
代码
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
string processCommand(string input) {
stringstream ss(input);
string cmd1, cmd2;
ss >> cmd1;
ss >> cmd2;
// 处理单个命令的情况
if (cmd2.empty()) {
string reset = "reset";
if (cmd1.size() <= reset.size() && reset.substr(0, cmd1.size()) == cmd1)
return "reset what";
return "unknown command";
}
// 处理两个命令的情况
string reset = "reset";
string board = "board";
string reboot = "reboot";
string backplane = "backplane";
string add = "add";
string del = "delete";
string abort = "abort";
// 检查第一个命令的匹配
bool isReset = cmd1.size() <= reset.size() && reset.substr(0, cmd1.size()) == cmd1;
bool isBoard = cmd1.size() <= board.size() && board.substr(0, cmd1.size()) == cmd1;
bool isReboot = cmd1.size() <= reboot.size() && reboot.substr(0, cmd1.size()) == cmd1;
bool isBackplane = cmd1.size() <= backplane.size() && backplane.substr(0, cmd1.size()) == cmd1;
int firstMatchCount = isReset + isBoard + isReboot + isBackplane;
if (firstMatchCount != 1) {
return "unknown command";
}
// 检查第二个命令的匹配
if (isReset && cmd2.size() <= board.size() && board.substr(0, cmd2.size()) == cmd2) {
return "board fault";
}
if (isBoard) {
if (cmd2.size() <= add.size() && add.substr(0, cmd2.size()) == cmd2) {
return "where to add";
}
if (cmd2.size() <= del.size() && del.substr(0, cmd2.size()) == cmd2) {
return "no board at all";
}
}
if (isReboot && cmd2.size() <= backplane.size() && backplane.substr(0, cmd2.size()) == cmd2) {
return "impossible";
}
if (isBackplane && cmd2.size() <= abort.size() && abort.substr(0, cmd2.size()) == cmd2) {
return "install first";
}
return "unknown command";
}
int main() {
string line;
while (getline(cin, line)) {
cout << processCommand(line) << endl;
}
return 0;
}
import java.util.*;
public class Main {
public static String processCommand(String input) {
String[] parts = input.split(" ");
String cmd1 = parts[0];
String cmd2 = parts.length > 1 ? parts[1] : "";
// 处理单个命令的情况
if (cmd2.isEmpty()) {
String reset = "reset";
if (cmd1.length() <= reset.length() && reset.substring(0, Math.min(cmd1.length(), reset.length())).equals(cmd1))
return "reset what";
return "unknown command";
}
// 处理两个命令的情况
String reset = "reset";
String board = "board";
String reboot = "reboot";
String backplane = "backplane";
String add = "add";
String del = "delete";
String abort = "abort";
// 检查第一个命令的匹配
boolean isReset = cmd1.length() <= reset.length() && reset.substring(0, Math.min(cmd1.length(), reset.length())).equals(cmd1);
boolean isBoard = cmd1.length() <= board.length() && board.substring(0, Math.min(cmd1.length(), board.length())).equals(cmd1);
boolean isReboot = cmd1.length() <= reboot.length() && reboot.substring(0, Math.min(cmd1.length(), reboot.length())).equals(cmd1);
boolean isBackplane = cmd1.length() <= backplane.length() && backplane.substring(0, Math.min(cmd1.length(), backplane.length())).equals(cmd1);
int firstMatchCount = (isReset ? 1 : 0) + (isBoard ? 1 : 0) + (isReboot ? 1 : 0) + (isBackplane ? 1 : 0);
if (firstMatchCount != 1) {
return "unknown command";
}
// 检查第二个命令的匹配
if (isReset && cmd2.length() <= board.length() && board.substring(0, Math.min(cmd2.length(), board.length())).equals(cmd2)) {
return "board fault";
}
if (isBoard) {
if (cmd2.length() <= add.length() && add.substring(0, Math.min(cmd2.length(), add.length())).equals(cmd2)) {
return "where to add";
}
if (cmd2.length() <= del.length() && del.substring(0, Math.min(cmd2.length(), del.length())).equals(cmd2)) {
return "no board at all";
}
}
if (isReboot && cmd2.length() <= backplane.length() && backplane.substring(0, Math.min(cmd2.length(), backplane.length())).equals(cmd2)) {
return "impossible";
}
if (isBackplane && cmd2.length() <= abort.length() && abort.substring(0, Math.min(cmd2.length(), abort.length())).equals(cmd2)) {
return "install first";
}
return "unknown command";
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
String line = sc.nextLine();
System.out.println(processCommand(line));
}
}
}
def process_command(input_str):
parts = input_str.split()
cmd1 = parts[0]
cmd2 = parts[1] if len(parts) > 1 else ""
# 处理单个命令的情况
if not cmd2:
reset = "reset"
if len(cmd1) <= len(reset) and cmd1 == reset[:len(cmd1)]:
return "reset what"
return "unknown command"
# 处理两个命令的情况
reset = "reset"
board = "board"
reboot = "reboot"
backplane = "backplane"
add = "add"
delt = "delete"
abort = "abort"
# 检查第一个命令的匹配
is_reset = len(cmd1) <= len(reset) and cmd1 == reset[:len(cmd1)]
is_board = len(cmd1) <= len(board) and cmd1 == board[:len(cmd1)]
is_reboot = len(cmd1) <= len(reboot) and cmd1 == reboot[:len(cmd1)]
is_backplane = len(cmd1) <= len(backplane) and cmd1 == backplane[:len(cmd1)]
first_match_count = sum([is_reset, is_board, is_reboot, is_backplane])
if first_match_count != 1:
return "unknown command"
# 检查第二个命令的匹配
if is_reset and len(cmd2) <= len(board) and board[:len(cmd2)] == cmd2:
return "board fault"
if is_board:
if len(cmd2) <= len(add) and add[:len(cmd2)] == cmd2:
return "where to add"
if len(cmd2) <= len(delt) and delt[:len(cmd2)] == cmd2:
return "no board at all"
if is_reboot and len(cmd2) <= len(backplane) and backplane[:len(cmd2)] == cmd2:
return "impossible"
if is_backplane and len(cmd2) <= len(abort) and abort[:len(cmd2)] == cmd2:
return "install first"
return "unknown command"
while True:
try:
line = input().strip()
print(process_command(line))
except:
break
算法及复杂度
- 算法:字符串匹配和条件判断
- 时间复杂度:
,每次处理命令的时间是常数级别
- 空间复杂度:
,只需要常数级别的额外空间
这个解法通过分类处理不同的输入情况,使用字符串前缀匹配来实现"最短唯一匹配原则"。代码结构清晰,易于维护和扩展。