查找包含公共字符的两个字符串的最快算法

Question

我想找出两个 Java 字符串是否包含 2 个必须彼此相邻的公共字符。

我正在使用两个 for 循环来检查它，但它看起来很慢，因为我必须一次又一次地计算它。

boolean contain2CommonChars(String s1, String s2) {

     for(){

       for() {

       }

    }

}

有没有有效的算法来做到这一点？

其次，我真正想做的是在给定另一个句子x的情况下，从一个大句子集B中找到一个句子子集A。如果 B 中的任何句子与句子 x 至少有两个共同字符，则将其放入集合 A。

Set<String> findSubset(Set<String> B, String x){

    Set<String> A = new HashSet<>();

    ...

    return A;      

}

顺便说一下，B <10,000 的大小。findSubset() 可以在几毫秒内完成吗？

编辑：第二个问题与第一个问题相关。例子：

B = {"this is a dog", "this is a bat", "that was an dog "}

x = "this is not a cat"

我要回：

A = {"this is a dog", "this is a cat"} //  because of "this is" or "is a"

Answer 1

查找两个 Java 字符串是否包含 2 个必须彼此相邻的公共字符。可能有很多边缘情况，但这是一种方法（可能不是最快的，但可以根据您的需要工作）。分别迭代两个字符串并HashSets为所有 2 字符对创建两个字符串。例如，foobar-->&nbsp;fo,&nbsp;oo,&nbsp;ob,&nbsp;ba,ar只需取上面创建的交集，HashSets看看是否有任何公共对。第二个问题很难理解。也许尝试包含一个示例以使其更清楚。

Answer 2

通过迭代 2 个字符串中最短的每个相邻对：static boolean contain2CommonChars(String s1, String s2) {&nbsp; &nbsp; int l1 = s1.length();&nbsp; &nbsp; int l2 = s2.length();&nbsp; &nbsp; if ((l1 < 2) || (l2 < 2))&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; if (l2 < l1) {&nbsp; &nbsp; &nbsp; &nbsp; String temp = s1;&nbsp; &nbsp; &nbsp; &nbsp; s1 = s2;&nbsp; &nbsp; &nbsp; &nbsp; s2 = temp;&nbsp; &nbsp; }&nbsp; &nbsp; for (int i = 0; i < s1.length() - 1; i++){&nbsp; &nbsp; &nbsp; &nbsp; String pair = s1.substring(i, i + 2);&nbsp; &nbsp; &nbsp; &nbsp; if (s2.contains(pair))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; return false;}public static void main(String[] args) {&nbsp; &nbsp; String s1 = "abcghj";&nbsp; &nbsp; String s2 = "shhcgop";&nbsp; &nbsp; System.out.println(s1 + " and " + s2 + " " + contain2CommonChars(s1, s2));&nbsp; &nbsp; String s3 = "abcghjlo";&nbsp; &nbsp; String s4 = "shhcop";&nbsp; &nbsp; System.out.println(s3 + " and " + s4 + " " + contain2CommonChars(s3, s4));}印刷abcghj and shhcgop trueabcghjlo and shhcop false

Answer 3

只回答第一个问题。如果您有可能对字符串进行预处理，则为每个字符串生成所有字符对并逐渐对它们进行排序。contain2CommonChars&nbsp;->&nbsp;2C&nbsp;ai&nbsp;ar&nbsp;Ch&nbsp;co&nbsp;Co&nbsp;ha&nbsp;in&nbsp;mm&nbsp;mo&nbsp;n2&nbsp;nC&nbsp;nt&nbsp;om&nbsp;on&nbsp;on&nbsp;rs&nbsp;ta现在两个字符串之间的公共对可以通过一次最多为 O(L) 的类似合并的传递找到。