Java算法---密码验证合格程序

　　这是一道华为oj上的字符串题目，分享一下。

题目描述：

密码要求:1.长度超过8位

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

3.不能有相同长度超2的子串重复说明:长度超过2的子串

输入描述：

一组或多组长度超过2的子符串。每组占一行

输出描述：

如果符合要求输出：OK，否则输出NG

测试用例：

021Abc9000

021Abc9Abc1

021ABC9000

021$bc9000

输出：

OK NG NG OK

分析一下这道题，其实前两个条件好判断，比较难的是第三个，先说一下第二个，这个怎么去实现，题目中说至少三种，我们可以这样去做，定义一个flag，如果满足条件就加1，这样我们最终只需判断flag的值，如果大于等于3，就满足，否则不满足。代码如下：

<pre name="code" class="plain"> public static int Con(String str){
        int count=0;
        if(str.length()-str.replaceAll("[A-Z]","").length()>0){//如果长度减少了，说明存在大写字母
            count++;
        }
        if(str.length()-str.replaceAll("[a-z]","").length()>0){//如果长度减少了，说明存在小写字母
            count++;
        }
        if(str.length()-str.replaceAll("[0-9]","").length()>0){
            count++;
        }
        if(str.replaceAll("[0-9,A-Z,a-z]","").length()>0){//如果长度大于零，说明存在其他字母
            count++;
        }
        return count;
    }

第三个条件呢，其实是要找一串字符串中，重复的字串长度，如果大于2就不符合。例如ABCX1&ABC,中ABC重复了，由于长度超过2，所以不符合。这道题呢021Abc9Abc1

Java算法---密码验证合格程序

看上图，这个图是按这个规则画的，如果字符串相等，dp[i][j]=dp[i-1][j-1]+1,否则为0，那么我们发现除了对角线部分的数字以外，其余部分的数字中，1,2,3出现了两次，如图红色字体，那么我们就可以得到长度为3的字串重复出现了两次，这样这个问题就基本解决。

下来我们只需要遍历这个二维矩阵，不过得加个条件，对角线上的数字不做统计，只需要判断大于二，相同的数字出现的次数，如果次数大于2则不否合要求。用一个一维数组统计出对角线以外的数字出现的个数，然后从3开始遍历，如果存在a[i]>1，说明长度大于2且出现了至少两次，直接输出不合格。

这样这个条件就解决了，当然如果你有更好的想法，或者更优化的方法，欢迎分享，我这并不是最好的解法，下面贴上自己的代码：

<span style="font-family:SimSun;font-size:18px;">import java.util.Scanner;
/**
 * Created by Administrator on 2015/12/17.
 */
public class Main1 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            String str=sc.next();
            if(str.length()>8&&Con(str)>=3&&Ischongfu(str)){
                System.out.println("OK");
            }else {
                System.out.println("NG");
            }
        }
    }
    public static int Con(String str){
        int count=0;
        if(str.length()-str.replaceAll("[A-Z]","").length()>0){
            count++;
        }
        if(str.length()-str.replaceAll("[a-z]","").length()>0){
            count++;
        }
        if(str.length()-str.replaceAll("[0-9]","").length()>0){
            count++;
        }
        if(str.replaceAll("[0-9,A-Z,a-z]","").length()>0){
            count++;
        }
        return count;
    }
    public static boolean Ischongfu(String str){
        int [][] dp=new int[str.length()+1][str.length()+1];
        for(int i=0;i<str.length();i++){
            for(int j=0;j<str.length();j++) {
                if(str.charAt(i)==str.charAt(j)){
                    dp[i+1][j+1]=dp[i][j]+1;
                }
            }
        }
        int [] a=new int[str.length()];
        for(int i=0;i<=str.length();i++){
            for(int j=0;j<=str.length();j++) {
                if(str.charAt(i)!=str.charAt(j)) {
                    a[dp[i][j]]++;
                }
            }
        }
        for(int i=3;i<a.length;i++){
            if(a[i]>1){
                return false;
            }
        }
        return true;
    }
}</span>

秒客网

Java算法---密码验证合格程序

相关文章