0

所以我有字符串数组，我想看看是否有（包含）其他字符串作为字符串的一部分。

例如，考虑以下简单数组。

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)，对吗？

4

3 回答 3

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 * 字符串比较时间)，这是对您的算法的改进（尽管一个非常轻微的改进，但我认为该算法也更容易实现和遵循）。

于 2016-10-25T20:08:40.987 回答
0

对于大量字符串和相对较短的字符串还有另一种可能性。它的计算复杂度为 O(n log(n) + n k^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));
    }
于 2016-10-26T09:13:36.990 回答
0

我将其作为答案做出回应，因为 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());
    }
}

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

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

于 2016-10-26T12:15:53.097 回答