最快的算法中搜索字符集给定字符串中 [英] Fastest algo for searching set of characters in given string

问题描述

这是一个辩论，我在和我的一个朋友：什么是做一个检查，如果给定的字符串有不允许的字符中的一个valiation方法的最快方法

This is a debate I was having with one of my friends: What would be the fastest way of making a valiation method that checks if the given string has one of the non-allowed characters

方法一：简单

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）

Method II: Exploiting Map's 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;
        }

该方法我其实是N2但当invalidChars较少的数量为好为N。 应该是什么preferred当案例一：有很多无效字符的，案例二：只有少数无效字符

The method I is actually N2 but as good as N when invalidChars are less in number. What should be preferred when Case I: There are lots of invalid chars, Case II: only few invalid chars?

注：我不找任何内置的Java解决方案，但是，仅仅是算法来过滤一些（不是全部）的非文本字符

Note: I'm not looking for any inbuilt java solutions but, just the algorithm to filter few (not all) non-text characters

推荐答案

如果你只关心确认ASCII字符，那么长度为128布尔查找表的可以的是比任何快上述方法

If you're only interested in validating ASCII characters, then a length-128 boolean lookup-table may be faster than either of the above methods.

这篇关于最快的算法中搜索字符集给定字符串中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！