查找1个字符串中的每个字符是否存在于另一个字符串中,比O(n ^ 2)快

Question

给出2个字符串:

String stringA = "WHATSUP";
String stringB = "HATS";

我想知道stringB H A T S中的每个字符是否都存在stringA

在初级方法中,该过程可以在嵌套的for循环内完成,其计算复杂度为O(n ^ 2).

for(int i = 0; i < stringA.length(); i++){
    for(int j = 0; j < stringB.length(); j++){
        if(stringA.charAt(i) == stringB.charAt(j))
            //do something
    }
}

我正在寻找一个更快的解决方案来解决这个问题.

Answer 1

有一个线性时间算法.

1. 将您转换stringA为具有O(1)成员资格测试的哈希字符集.
2. 迭代每个角色stringB.
3. 如果其中一个字符不在您的哈希集中,则测试失败.
4. 如果没有失败,则测试成功.