查找首个重复字符串算法

本文主要是介绍查找首个重复字符串算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/**
* 例“abncdbmn”,首个重复字母为b
*/
package cn.edu.moon.alg;

import java.util.BitSet;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
* @author Administrator
*
*/
public class FindSameChar {

    public char findSameChar(String str){
        int length = str.length();
        for(int i = 0;i<length;i++)
            for(int j=i+1;j<length;j++)
            {
                if(str.charAt(i)==str.charAt(j)){
                    return str.charAt(i);
                }
            }
        return 0;
    }

    public char findSameMap(String str){
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i=0;i<str.length();i++){
            if(map.containsKey(str.charAt(i))){
                return str.charAt(i);
            }else
            {
                map.put(Character.valueOf(str.charAt(i)), Integer.valueOf(1));
            }
        }
        return 0;
    }

    public char findSameBitSet(String str) {
        BitSet set = new BitSet(255);
        for (int i = 0; i < str.length(); i++) {
            if (set.get(str.charAt(i))) {
                return str.charAt(i);
            } else {
                set.set(str.charAt(i), true);
            }
        }
        return 0;
    }

    private static final Pattern p = Pattern.compile("(\\w).*\\1");

    public String findSameRegEx(String s) {
        Matcher m = p.matcher(s);
        if (m.find()) {
            return m.group(1);
        } else {
            return null;
        }
    }

    private static final long TIMES = 100*1000*1000;

    public static void main(String[] args) {
        char result = 0;
        FindSameChar test = new FindSameChar();
        long t = System.currentTimeMillis();
        for (long i = 0; i < TIMES; i++) {
            result = test.findSameChar("abcdefghijklmnopqrstbab");
        }
        t = System.currentTimeMillis() - t;
        System.out.println("findSameChar : Result " + result + " in " + t);

        result = 0;
        t = System.currentTimeMillis();
        for (long i = 0; i < TIMES; i++) {
            result = test.findSameMap("abcdefghijklmnopqrstbab");
        }
        t = System.currentTimeMillis() - t;
        System.out.println("findSameMap : Result " + result + " in " + t);

        result = 0;
        t = System.currentTimeMillis();
        for (long i = 0; i < TIMES; i++) {
            result = test.findSameBitSet("abcdefghijklmnopqrstbab");
        }
        t = System.currentTimeMillis() - t;
        System.out.println("findSameBitSet : Result " + result + " in " + t);

        String strResult = null;
        t = System.currentTimeMillis();
        for (long i = 0; i < TIMES; i++) {
            strResult = test.findSameRegEx("abcdefghijklmnopqrstbab");
        }
        t = System.currentTimeMillis() - t;
        System.out.println("findSameRegEx : Result " + strResult + " in " + t);
    }
}
/**
* 运行结果，原以为findSameMap最快，哈哈，最终最简单的总是最快的
   findSameChar : Result a in 10547
   findSameMap : Result b in 246000
   findSameBitSet : Result b in 76328
   findSameRegEx : Result a in 127187
*/