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

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--> fo, oo, ob, ba,ar

• 只需取上面创建的交集，HashSets看看是否有任何公共对。

第二个问题很难理解。也许尝试包含一个示例以使其更清楚。

Answer 2

通过迭代 2 个字符串中最短的每个相邻对：

static boolean contain2CommonChars(String s1, String s2) {

    int l1 = s1.length();

    int l2 = s2.length();

    if ((l1 < 2) || (l2 < 2))

        return false;

    if (l2 < l1) {

        String temp = s1;

        s1 = s2;

        s2 = temp;

    }

    for (int i = 0; i < s1.length() - 1; i++){

        String pair = s1.substring(i, i + 2);

        if (s2.contains(pair))

            return true;

    }

    return false;

}

public static void main(String[] args) {

    String s1 = "abcghj";

    String s2 = "shhcgop";

    System.out.println(s1 + " and " + s2 + " " + contain2CommonChars(s1, s2));

    String s3 = "abcghjlo";

    String s4 = "shhcop";

    System.out.println(s3 + " and " + s4 + " " + contain2CommonChars(s3, s4));

}

印刷

abcghj and shhcgop true

abcghjlo and shhcop false

Answer 3

只回答第一个问题。

---

如果您有可能对字符串进行预处理，则为每个字符串生成所有字符对并逐渐对它们进行排序。

contain2CommonChars -> 2C ai ar Ch co Co ha in mm mo n2 nC nt om on on rs ta

现在两个字符串之间的公共对可以通过一次最多为 O(L) 的类似合并的传递找到。