我有一个蛮力解决方案来在 O(n^2) 时间内计算输入字符串中的所有子字符串。当我的输入字符串很长时,它需要很长时间。
我们如何在 O(n) 时间内找到所有可能的子串?
我只是在寻找所有子字符串的计数,其中子字符串中的第一个和最后一个字符是相同的。正如您所看到的,我只在下面的代码中从函数返回计数。我想在 O(n) 时间内完成
我的蛮力解决方案:
// I am calculating count of all substrings where first and last substring character are equal
public class Solution {
public static void main(String[] args) {
String inputString = "ababaca";
System.out.println(findSubstringByBruteForcce(inputString, inputString.length()));
}
private static long findSubstringByBruteForcce(String inputString, int length) {
long count = 0;
for (int i = 0; i < length; i++) {
for (int j = 1; j <= length - i; j++) {
String str = inputString.substring(i, i + j);
if(str.length() == 1){
count = count + 1;
}else {
if(str.substring(0, 1).equals(str.substring(str.length() - 1, str.length()))){
count = count + 1;
}
}
}
}
return count;
}
}
如何优化上述解决方案并在 O(N) 时间内找到答案?输入字符串可能非常大(大约 10^6 长度)并且蛮力运行大约需要 20 秒。我希望最大运行时间低于 2 秒。
最佳答案
由于子串身份由边界索引而不是内容决定,因此计算每个字母的频率就足够了,然后对于每个字母,将项 (频率 + 1) * 频率 div 2 相加,因为每对字母位置与重复但不考虑顺序会产生一个计数的子串。
关于java - 是否有一种技巧/算法可以让我们在 O(n) 时间内找到所有可能的子串,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30960667/