Java

Question

所以我有一个字符串数组，我想看看其中是否有（包含）其他字符串。

例如，考虑下面的简单数组。

s[0]="Java"
s[1]="Java Programming"
s[2]="C Programming"
s[3]="C Programming is Cool"

到最后，我只想保留

s[1]="Java Programming"
s[3]="C Programming is Cool"

因为s[1]包含s[0]，s[3]包含s[2]。

这是我使用 String.Contains() 方法检测数组元素是否包含数组元素的代码，这看起来非常基础且效率低下..

int startPtr = 0;
while (startPtr < s.length-1) {
    int tempPtr = startPtr+1;
    while (tempPtr <= s.length-1) {
        if (s[tempPtr].contains(s[startPtr])) { 
            //At this point, I know that I don't need s[startPtr] in result.
            //Remove item at startPtr, if this were ArrayList or something.
            startPtr++;
            break; 
    } else { indexPtr++; }
}

并且在 startPtr 到达结尾后，我想我必须以相反的顺序做同样的事情（从结尾开始并检查数组的开头）以确保没有字符串是其他字符串元素的一部分。

有人可以帮我改进算法吗？另外，我相信这个算法的复杂度为 O(N^2)，对吗？

Answer 1

我建议先按长度递减的顺序对 s 中的字符串进行排序。这样做之后，当遍历 s 时，每个字符串都不能包含在 s 中后面的字符串中，因为后面的字符串长度更短。因此，您只需遍历 s 一次，无需执行任何回溯。

List<String> finalStrs = new ArrayList<>();
// You will have to create decreasingLengthComparator
Arrays.sort(s, decreasingLengthComparator);
for (String str : s) {
    boolean addToFinal = true;
    for (String finalStr : finalStrs) {
        if (finalStr.contains(str)) {
            addToFinal = false;
            break;
        }
    }
    if (addToFinal) {
        finalStrs.add(str);
    }
}

排序的效率是O(nlog(n))。迭代 s 并检查字符串是否在 finalStrs 中的效率是 O(n^2 / 2)*O(字符串比较时间)。

这样一来，整体复杂度为O(nlog(n) + n^2 / 2 * 字符串比较时间) = O(n^2 / 2 * 字符串比较时间)，这是一个改进超过你的算法（虽然有很小的改进，但我认为该算法也更容易实现和遵循）。

Answer 2

还有一种可能是字符串数量多，字符串比较短。它的计算复杂度为 O(nlog(n) + nk^2*log(n*k))，其中 n 是字符串的数量，k 是最长字符串的长度。

想法是创建已包含在结果集中的字符串的所有可能子串的查找集，并检查该集中是否存在。

在最坏的情况下，查找集中会有 n*k^2/2 个不同的字符串。

TreeSet<String> containedStrings = new TreeSet<>();
List<String> finalStrs = new ArrayList<>();
// You will have to create decreasingLengthComparator
Arrays.sort(s, decreasingLengthComparator);
for (String str : s) 
    if (!containedStrings.contains(str))
        finalStrs.add(str);
        for (int i = 0; i < s.length(); i++)
            for (int j = i+1; j <= s.length(); j++)
                containedStrings.add(s.substring(i, j));
    }

Answer 3

我将此回复作为回答，因为 OP 要求提供更多关于我对 mapeter 回答的评论的信息。重申一下，mapeter 解决方案的关键在于他将项目添加到新列表而不是将它们从列表中删除，确保删除的项目不会弄乱指针算法并导致越界错误。但是，这也可以通过反向遍历数组来就地完成：

Collections.sort(s, new LengthCompare());
for (int i = s.size() - 1; i >= 1; i--)
{
    for (int j = i-1; j >= 0; j--)
    {
        if (s[j].contains(s[i]))
        {
            s.remove(i)
            break;
        }
    }
}

private static class LengthCompare implements Comparator<String>
{
    public int compare(String s1, String s2)
    {
        return (s2.length() - s1.length());
    }
}

当然，由于原始数组的大小是固定的，这仅适用于列表（在没有看到其中的其余代码的情况下，我不明白为什么你不能使用它）。

此外，我还没有测试过这是否真的可以编译。这只是伪代码，我可能混合了数组和列表类型，但形式还是一样。

Java - 字符串数组 - 检查某个元素是否是另一个字符串的一部分（未找到 "Duplicates"）

Java - Array of String - check if certain element is PART of other string (not finidng "Duplicates")

string

algorithm

contains

coding-efficiency