如何优化最长无禁用词子串求解算法以降低时间复杂度？

问题描述 #

给定一个无空格字符串（长度范围1_{10^5）和一个无空格单词列表（列表大小1}10，单个单词长度1~10），需要找出最长的子串，要求该子串中不包含列表里的任何单词。

约束条件 #

• 输入字符串长度为1到10^5，无空格
• 单词列表大小为1到10，所有单词均无空格，单个单词长度为1到10

示例 #

s = "helloworld"
words = ["wor", "rld"]

结果：符合要求的最长子串是hellowo，它不包含"wor"和"rld"，长度为7。

现有实现 #

我写了一段代码，在小输入规模下可以正常运行：

int solve(String s, List<String> list) {
    int answer = 0, j=0;
    for(int i = 0 ; i <= s.length(); i++) {
        String sub = s.substring(j, i);
        for(String e : list) {
            if(sub.contains(e)){
                j = j+1;
                sub = s.substring(j, i);
            }
        }
        answer = Math.max(answer, i-j);
    }
    return answer;
}

这段代码的时间复杂度为O(m*n²)，其中n是输入字符串的长度，m是单词列表的大小。

编辑说明：根据meriton的解释更新了时间复杂度。

需求 #

现寻求更优的实现方案，降低算法的时间复杂度。

内容的提问来源于stack exchange，提问作者Learner