Hard

题目描述

给你一个字符串 word 和一个字符串数组 forbidden。

如果一个字符串的任何子字符串都不在 forbidden 中，则称该字符串为 有效 的。

返回字符串 word 中最长有效子字符串的长度。

子字符串 是字符串中连续的字符序列，可能为空。

示例 1：

输入：word = "cbaaaabc", forbidden = ["aaa","cb"]
输出：4
解释：word 中有 11 个有效子字符串："c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" 和 "aabc"。最长有效子字符串的长度为 4。
可以证明所有其他子字符串都包含 "aaa" 或 "cb" 作为子字符串。

示例 2：

输入：word = "leetcode", forbidden = ["de","le","e"]
输出：4
解释：word 中有 11 个有效子字符串："l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod" 和 "tcod"。最长有效子字符串的长度为 4。
可以证明所有其他子字符串都包含 "de", "le" 或 "e" 作为子字符串。

提示：

  • 1 <= word.length <= 10^5
  • word 仅由小写英文字母组成
  • 1 <= forbidden.length <= 10^5
  • 1 <= forbidden[i].length <= 10
  • forbidden[i] 仅由小写英文字母组成

解题思路

解题思路

这是一道典型的滑动窗口问题。我们需要找到最长的子字符串，使其不包含任何禁止的子字符串。

主要思路：

  1. 预处理禁止词汇：将所有禁止的字符串存储在哈希集合中，便于快速查找
  2. 滑动窗口：维护一个窗口 [left, right]，确保窗口内的子字符串不包含任何禁止词汇
  3. 窗口扩展与收缩：
    • 右指针不断扩展窗口
    • 当发现窗口内包含禁止词汇时，收缩左边界
  4. 优化检查：由于禁止词汇长度最大为10，我们只需要检查以当前右端点结尾的最多10个字符的子字符串

关键优化点：

  • 不需要检查所有可能的子字符串，只需检查以当前位置结尾、长度不超过禁止词汇最大长度的子字符串
  • 当发现禁止词汇时，将左指针移动到该禁止词汇结束位置的下一个位置

时间复杂度分析：

  • 外层循环：O(n)
  • 内层检查：最多检查10个字符，每次检查最多10个长度，所以是O(100) = O(1)
  • 总体：O(n)

代码实现

class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        unordered_set<string> forbiddenSet(forbidden.begin(), forbidden.end());
        int n = word.length();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            // 检查以right结尾的所有可能的禁止子字符串
            for (int len = 1; len <= min(10, right - left + 1); len++) {
                string substr = word.substr(right - len + 1, len);
                if (forbiddenSet.count(substr)) {
                    left = right - len + 2; // 移动到禁止子字符串后的位置
                    break;
                }
            }
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        n = len(word)
        left = 0
        max_len = 0
        
        for right in range(n):
            # 检查以right结尾的所有可能的禁止子字符串
            for length in range(1, min(11, right - left + 2)):
                if right - length + 1 < left:
                    break
                substr = word[right - length + 1:right + 1]
                if substr in forbidden_set:
                    left = right - length + 2  # 移动到禁止子字符串后的位置
                    break
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int LongestValidSubstring(string word, IList<string> forbidden) {
        var forbiddenSet = new HashSet<string>(forbidden);
        int n = word.Length;
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            // 检查以right结尾的所有可能的禁止子字符串
            for (int len = 1; len <= Math.Min(10, right - left + 1); len++) {
                if (right - len + 1 < left) break;
                string substr = word.Substring(right - len + 1, len);
                if (forbiddenSet.Contains(substr)) {
                    left = right - len + 2; // 移动到禁止子字符串后的位置
                    break;
                }
            }
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function(word, forbidden) {
    const forbiddenSet = new Set(forbidden);
    const n = word.length;
    let left = 0, maxLen = 0;
    
    for (let right = 0; right < n; right++) {
        // 检查以right结尾的所有可能的禁止子字符串
        for (let len = 1; len <= Math.min(10, right - left + 1); len++) {
            if (right - len + 1 < left) break;
            const substr = word.substring(right - len + 1, right + 1);
            if (forbiddenSet.has(substr)) {
                left = right - len + 2; // 移动到禁止子字符串后的位置
                break;
            }
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为字符串长度，每个位置最多检查10个长度的子字符串，常数时间
空间复杂度O(m×k)m为禁止词汇数量，k为禁止词汇平均长度，用于存储哈希集合