测试字符串是否是字符串列表中任何字符串的子字符串的有效方法

Question

我想知道将字符串与字符串列表进行比较的最佳方法。这是我心中的代码，但很明显它在时间复杂度方面并不好。

for (String large : list1) {
    for (String small : list2) {
        if (large.contains(small)) {
            // DO SOMETHING
        } else {
            // NOT FOR ME
        }
    }

    // FURTHER MANIPULATION OF STRING 
}

两个字符串列表都可以包含超过一千个值，所以最坏的情况复杂度可以上升到 1000×1000×length，这是一团糟。我想知道在上面给定的场景中执行比较字符串和字符串列表任务的最佳方法。

Answer 1

不幸的是，这是一个困难而混乱的问题。这是因为您正在检查一个小字符串是否是一堆大字符串的 子字符串 ，而不是检查小字符串是否等于一堆大字符串。

最佳解决方案取决于您需要解决的具体问题，但这是合理的第一次尝试：

在一个临时的地方，将所有的大字符串连接在一起，然后在这个连接起来的长字符串上构造一个suffix tree。有了这个结构，我们应该能够在所有 large 中快速找到任何给定 small 的所有子串匹配。

Answer 2

你可以这样做：

 for (String small : list2) {
    if (set1.contains(small)) {
        // DO SOMETHING
    } else {
        // NOT FOR ME
    }
}

set1 应该是较大的字符串列表，而不是将其保留为 List<String>，而是使用 Set<String> 或 HashSet<String>

Answer 3

感谢 sandeep 的第一个回答。这是解决方案：

List<String> firstCollection = new ArrayList<>();
Set<String> secondCollection = new HashSet<>();

//POPULATE BOTH LISTS HERE.

for(String string: firstCollection){
    if(secondCollection.contains(string)){
        //YES, THE STRING IS THERE IN THE SECOND LIST
    }else{
        //NOPE, THE STRING IS NOT THERE IN THE SECOND LIST
    }
}

测试字符串是否是字符串列表中任何字符串的子字符串的有效方法

Efficient way to test if a string is substring of any in a list of strings

java

time-complexity

string-comparison