题目主要信息

1、检验输入的密码是否合格

2、密码要求如下

• 长度超过8位

• 密码要求:

  1.长度超过8位

  2.包括大小写字母.数字.其它符号,以上四种至少三种

  3.不能有长度大于2的不含公共元素的子串重复 （注：其他符号不含空格或换行）

方法一：暴力

具体方法

按照密码的要求，依次遍历验证即可。

1、首先验证长度是否大于8，不满足直接输出NG并继续 2、验证是否包含三种以上的字符 3、验证是否存在重复子串，并且长度大于等于3 这里主要给出第三步的详解，前两步的直接遍历求解即可。 第三步可以使用类似窗口的方法，因为要求最长重复子串不能大于2，所以就把窗口的大小设置为3。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s = bf.readLine())!=null){
            //1.长度超过8位
            if(s.length() <= 8){
                System.out.println("NG");
                continue;
            }
            //2.包括大小写字母.数字.其它符号,以上四种至少三种
            int count[] = new int[4];//记录出现个数
            for(int i=0;i<s.length();i++){
                if(s.charAt(i) >= 'A'&& s.charAt(i)<='Z' ){
                    count[0] = 1;
                }else if(s.charAt(i) >= 'a'&& s.charAt(i)<='z' ){
                    count[1] = 1;
                }else if(s.charAt(i) >= '0'&& s.charAt(i)<='9' ){
                    count[2] = 1;
                }else {
                    count[3] = 1;
                }
            }
            if(count[0]+count[1]+count[2]+count[3]<3){
                System.out.println("NG");
                continue;
            }
            //3.不能有长度大于2的不含公共元素的子串重复 （注：其他符号不含空格或换行）
            if(getString(s,0,3)){
                System.out.println("NG");
                continue;
            } else {
                System.out.println("OK");
            }
        }
    }
    //检测是否存在长度大于3的重复子串
     static boolean getString(String str,int l,int r) {
         if (r >= str.length()) {
             return false;
         }
         if (str.substring(r).contains(str.substring(l, r))) {
             return true;
         } else {
             return getString(str, l + 1, r + 1);
         }
     }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，n为单次密码长度，验证重复子串两层循环遍历字符串
• 空间复杂度：$O(1)O(1)$，字符串s属于必要空间

方法二：正则表达式

具体做法

匹配小写字母、大写字母、数字、其他字符，还是匹配串中前后连续三个一样的字符，我们都可以用正则表达式。只要把正则表达式写出来即可

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = bf.readLine())!=null) {
            // 长度check, 相同长度超2的子串重复check
            if (s.length() <= 8 ) {
                System.out.println("NG");
                continue;
            }
            // 大小写字母.数字.其它符号check
            String[] regexes = {"\\d", "[a-z]", "[A-Z]", "[^\\da-zA-Z]"};
            int types = 0;
            for (String re : regexes) {
                Pattern p = Pattern.compile(re);
                Matcher m = p.matcher(s);
                if (m.find()) {
                    types += 1;
                }
            }
            if(types<3){
                System.out.println("NG");
                continue;
            }
          //匹配串前后连续3个字符一样的 
         //public String replaceAll(String replacement)
		 //替换模式与给定替换字符串相匹配的输入中存在长度大于2的不含公共元素的子串重复 删除一个重复字串长度显然变短了 这时输入NG
            if(s.replaceAll("(.{3,})(?=.{3,}\\1)", "").length() < s.length()){
                System.out.println("NG");
                continue;
            }
            System.out.println("OK");
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，正则表达式匹配复杂度为$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数级空间，字符串s属于必要空间