题目分析

1. 题目给出我们若干条字符串，其含义是我们经常会注册登录所使用的密码
2. 题目对密码格式进行要求

• 第一点：密码必须超过8位
• 第二点：必须有大写字母、小写字母、数字、符号四种中的三种
• 第三点：密码不能有重复的公共子串，公共子串长度判定为3个字符及以上

4. 我们要输出其是否符合以上条件的判断结果，OK或者NG

• 思路
  • 对于第一点我们只要判断是否长度合法即可
  • 对于第二点我们可以准备要给列表分别表示四种情况的出现与否状态
    • 如果出现了对应类型的情况，则标记其值为1
    • 最后查看是否标记为1的种类满足三种的要求
  • 对于第三点是一个处理字符串的问题，我们分两种方法解决

方法一：暴力搜索

• 实现思路

  • 我们知道如果有不满足第三点的情况，不管公共部分的子串有多长，至少会出现3个字符的子串同时出现两次及以上的情况

  • 因此我们遍历取出所有的3字符的子串，并且暴力在剩余部分字符串中检查搜索

  • 直到检查到其不会出现重复子串完全合法才输出OK

  • 否则输出NG

def check(pw):
    if len(pw) <= 8:			# 判断密码的长度
        return False
    
    checks = [0,0,0,0]			# 四种情况满足三种的辅助列表
    for c in pw:
        if c.isupper():			# 大写字母
            checks[0] = 1
        elif c.islower():		# 小写字母
            checks[1] = 1
        elif c.isdigit():		# 数字
            checks[2] = 1
        else:					# 其他字符
            checks[3] = 1
    if sum(checks) < 3:
        return False
        
    
    for i in range(len(pw) - 2):		# 循环遍历找到子字符串的起点
        if pw[i:i+3] in pw[i+3:]:		# 在剩下的字符串中顺序查找匹配当前字符串
            return False
    
    return True



while True:
    try:
        pw = input()
        if check(pw):
            print('OK')
        else:
            print('NG')
    except:
        break

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，由于对于公共子串的检查和搜索进行了两轮查找工作，时间代价为平方级别
• 空间复杂度：$O(1)O(1)$，只有一个校验题目第二点的时候用到了常量级别的checks列表

方法二：借助字典辅助查找

• 实现思路
  • 暴力搜索的时间代价是平方级别的
  • 我们可以在遍历的过程中对于当前的未出现过的子字符串都存储在字典中
  • 在继续遍历的过程中直接根据字符串在字典中是否出现过来判断重复情况
  • 由于字典的组织形式是哈希表，因此大大减少了搜索时间的开销

def check(pw):
    if len(pw) <= 8:			# 判断密码的长度
        return False
    
    checks = [0,0,0,0]			# 四种情况满足三种的辅助列表
    for c in pw:
        if c.isupper():			# 大写字母
            checks[0] = 1
        elif c.islower():		# 小写字母
            checks[1] = 1
        elif c.isdigit():		# 数字
            checks[2] = 1
        else:					# 其他字符
            checks[3] = 1
    if sum(checks) < 3:
        return False
        
    dc = {}
    for i in range(len(pw) - 2):		# 遍历所有的子字符串起点
        if pw[i:i+3] in dc:				# 在字典中搜索
            return False
        else:							# 如果未曾经出现过则加入字典中，等待之后的判定
            dc[pw[i:i+3]] = 1
    
    return True



while True:
    try:
        pw = input()
        if check(pw):
            print('OK')
        else:
            print('NG')
    except:
        break

复杂度分析

• 时间复杂度：$O(n)O(n)$，只需要一次遍历字符串的时间代价
• 空间复杂度：$O(n)O(n)$，借助了字典空间代价，存储字符串的空间大小的开销