6924. 最长合法子字符串的长度 (opens new window)

1.双指针+时间优化

同向双指针维护合法字符串窗口。子串每次插入字符word[right]后进行合法性校验，因此如果出现非法子串，那么右指针总是作为非法词的后缀，故左指针都需要移动到最短非法词的起始下标。假设forbidden禁词表的长度为N，难点在于子字符串是否包含非法字符串判断的算法复杂度优化，有几下几种：

• 使用String.contains(forbidden集合)接口进行非法性校验，因此需要遍历forbidden集合每一个元素，所以每次合法性校验的算法复杂度O(N)。第一遍写超时
• 反过来,使用集合的contains接口判断子串是否非法。并且考虑到题目给出的非法词的长度不会超过10，即子串[left,right]只需要检验[right-10,right]部分，没必要从头遍历左指针移动。表面上这里时间复杂度O(1)，事实上ArrayList.contains底层是遍历所有元素，因此每次合法性校验时间复杂度O(N)
• 将ArrayList换成哈希进行合法性校验，因为是根据哈希key进行查询，因此HashSet.contains时间复杂度O(1)

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        int left=0;
        int res=0;
        Set<String> hash=new HashSet<>(forbidden);
        for(int i=0;i<word.length();i++){
            for(int j=i;j>=i-9;j--){
                if(j>=left&&hash.contains(word.substring(j,i+1))){
                    left=j+1;
                    break;
                }
            }
            res=Math.max(res,i-left+1);
        }
        return res;
    }
}

2.总结

本题难点不在算法实现，而是在算法效率优化上。判断字符串str和List<String>集合是否存在交集时：

• 遍历list集合取出每一个数，要进行N次str.contains(s)；而直接拿集合contains(strs)判断时只需要一次
• 如果集合是ArrayList时，底层会取出每个元素进行遍历，此时上面两种方法的时间复杂度差不多；如果集合采用HashSet，则直接根据str的哈希值定位到元素O(1)。