最快的算法,用于搜索给定字符串中的字符集

Question

这是我和我的一个朋友讨论的问题:制作一个valiation方法的最快方法是检查给定的字符串是否有一个不允许的字符

方法一:简单

char [] invalidChars = "!@#$%^...".toCharArray();
        for (int i = 0; i < myString.length(); i++) {
            char ch = myString.charAt(i);
            for (int j = 0; j < invalidChars.length; j++) {
                if (invalidChars[j] == ch) {
                    return false;
                }
            }
        }

方法二:利用地图的O(1)

Map <String,String> map = new HashMap<String, String>();
        map.put("!", null);
        map.put("@", null);
        map.put("#", null);
        map.put("$", null);
        map.put("^", null);
        ...
        for (int i = 0; i < labels.length(); i++) {
            char ch = labels.charAt(i);
            if (map.containsKey(ch)) {
                return false;
            }
            return true;
        }

方法I实际上是N2,但当invalidChars数量较少时,与N一样好.第一种情况应该优先考虑:有很多无效字符,案例二:只有少数无效字符？

注意:我不是在寻找任何内置的java解决方案,而只是用于过滤少数(非全部)非文本字符的算法

Answer 1

如果您只对验证ASCII字符感兴趣,那么长度为128的布尔查找表可能比上述任何一种方法都快.