题解 | #配置文件恢复#

配置文件恢复

http://www.nowcoder.com/practice/ca6ac6ef9538419abf6f883f7d6f6ee5

题目分析

题目给出了我们输入和输出的对应关系，输入一条指定的命令或可以补全后唯一确定的命令，输出对应的执行结果

我们需要合理处理对于输入命令的要求，匹配是否可以补全后成为唯一确定的命令，如果可以锁定唯一则输出相应的结果；如果不唯一则输出错误信息

方法一：切分

实现思路
- 在进行补全匹配时候，我们采用切分的方式进行匹配
- 首先我们要确定输入的关键字有多少个，根据数量进行分类讨论
- 由于我们知道缩写如'r'这种可以对应到'reset'命令上，因此切分的方式就是按照输入的字符串长度切分完整的字符串，匹配两者是否相同
  - 如果相同则认为其可以完整合法匹配，但是仍需要确定的问题是是否可以唯一匹配
    - 唯一匹配只需要遍历所有可能性，查看最后匹配的次数是否为1即可
  - 如果不同则直接输出错误信息

alt


def solution(command):
    un = "unknown command"
    key=["reset","reset board","board add","board delete","reboot backplane","backplane abort", "he he"]
    value=["reset what","board fault","where to add","no board at all","impossible","install first", un]
    if len(command) < 1 or len(command) > 2:        # 指令关键字数不匹配
        res = un
    elif len(command) == 1:                         # 指令只有一个关键字
        ins = command[0]
        if ins == key[0][:len(ins)]:				# 切分长度判断两者是否相同
            res = value[0]
        else:
            res = un
    else:                                           # 指令有两个关键字
        match = []
        for i in range(1, len(key)):
            ins1, ins2, cur = command[0], command[1], key[i].split()
            if ins1 == cur[0][:len(ins1)] and ins2 == cur[1][:len(ins2)]:		# 两个关键字的分别切分判断
                match.append(i)
        if len(match) > 1:
            res = un
        else:
            res = value[match[0]]
    return res


while True:
    try:
        command = input().strip().split()
        print(solution(command))
    except:
        break

复杂度分析

时间复杂度： $O (n)$ ，由于对于所有的字符串全部遍历一遍进行匹配操作
空间复杂度： $O (1)$ ，key和value两个规则序列所申请的空间大小是常量级别的

方法二：find函数

实现思路
- 上面的道理我们可以采用find函数来进行匹配操作
- find的使用方法是用key中的内容去检索是否给定的输入存在于key的开头部分，所以判断的结果是和下标0进行判断的
  - 如下标找到的确为0，则认为其可以完整合法匹配，但是仍需要确定的问题是是否可以唯一匹配
    - 唯一匹配只需要遍历所有key，查看最后匹配的次数是否为1即可
  - 如果非0则直接输出错误信息


def solution(command):
    un = "unknown command"
    key=["reset","reset board","board add","board delete","reboot backplane","backplane abort", "he he"]
    value=["reset what","board fault","where to add","no board at all","impossible","install first", un]
    if len(command) < 1 or len(command) > 2:        # 指令关键字数不匹配
        return un
    elif len(command) == 1:                         # 指令只有一个关键字
        ins = command[0]
        if key[0].find(ins) == 0:				    # 用ins去找其在key的索引是否为0
            return value[0]
        else:
            return un
    else:                                           # 指令有两个关键字
        match = []
        for i in range(1, len(key)):
            ins1, ins2, cur = command[0], command[1], key[i].split()
            if cur[0].find(ins1) == 0 and cur[1].find(ins2) == 0:			# 两个关键字则用空格拆开两个关键字后，分别切分用得到的字符串搜索在key中是否为下标0的位置
                match.append(i)
        if len(match) > 1:
            return un
        else:
            return value[match[0]]
    return ""


while True:
    try:
        command = input().strip().split()
        print(solution(command))
    except:
        break