Hard

题目描述

给你一个字符串 s 和一个模式字符串 p，其中 p 恰好包含两个 * 字符。

p 中的 * 匹配任意零个或多个字符的序列。

返回 s 中与 p 匹配的最短子串的长度。如果不存在这样的子串，返回 -1。

注意：空子串被认为是有效的。

示例 1：

输入：s = "abaacbaecebce", p = "ba*c*ce"
输出：8
解释：s 中与 p 匹配的最短子串是 "baecebce"。

示例 2：

输入：s = "baccbaadbc", p = "cc*baa*adb"
输出：-1
解释：s 中不存在匹配的子串。

示例 3：

输入：s = "a", p = "**"
输出：0
解释：空子串是最短的匹配子串。

示例 4：

输入：s = "madlogic", p = "*adlogi*"
输出：6
解释：s 中与 p 匹配的最短子串是 "adlogi"。

约束条件：

  • 1 <= s.length <= 10^5
  • 2 <= p.length <= 10^5
  • s 只包含小写英文字母
  • p 只包含小写英文字母和恰好两个 *

提示：

  • 模式字符串 p 可以分为三个段
  • 使用 KMP 算法在 s 中定位每个段的所有出现位置

解题思路

解题思路：

这道题需要在字符串 s 中找到与包含两个通配符的模式 p 匹配的最短子串。

首先分析模式的结构：由于 p 恰好包含两个 *，我们可以将其分为三段：

  • 前缀：第一个 * 之前的部分
  • 中缀：两个 * 之间的部分
  • 后缀：第二个 * 之后的部分

核心思路：

  1. 将模式 p 按两个 * 分割成三个部分（可能为空）
  2. 使用 KMP 算法分别在 s 中找到所有匹配的前缀和后缀位置
  3. 对于每个有效的前缀位置，寻找在其右侧能够匹配的最近后缀位置
  4. 在确定的前缀和后缀之间，验证是否能找到匹配的中缀
  5. 计算所有有效匹配的长度，返回最小值

特殊情况处理：

  • 如果前缀或后缀为空，相应的匹配位置可以是字符串的边界
  • 如果中缀为空，只需要确保前缀的结束位置不超过后缀的开始位置
  • 当模式为 ** 时，直接返回 0（空串匹配）

时间复杂度主要来自 KMP 预处理和字符串匹配，整体算法在处理大规模数据时表现良好。

代码实现

class Solution {
public:
    vector<int> computeLPS(const string& pattern) {
        int m = pattern.length();
        vector<int> lps(m, 0);
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    vector<int> findOccurrences(const string& text, const string& pattern) {
        vector<int> result;
        if (pattern.empty()) {
            for (int i = 0; i <= text.length(); i++) {
                result.push_back(i);
            }
            return result;
        }
        
        vector<int> lps = computeLPS(pattern);
        int i = 0, j = 0;
        int n = text.length(), m = pattern.length();
        
        while (i < n) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
            }
            
            if (j == m) {
                result.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && text[i] != pattern[j]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return result;
    }
    
    int shortestMatchingSubstring(string s, string p) {
        int first_star = p.find('*');
        int second_star = p.find('*', first_star + 1);
        
        string prefix = p.substr(0, first_star);
        string infix = p.substr(first_star + 1, second_star - first_star - 1);
        string suffix = p.substr(second_star + 1);
        
        vector<int> prefix_positions = findOccurrences(s, prefix);
        vector<int> suffix_positions = findOccurrences(s, suffix);
        
        int min_length = INT_MAX;
        
        for (int prefix_pos : prefix_positions) {
            int prefix_end = prefix_pos + prefix.length();
            
            for (int suffix_pos : suffix_positions) {
                int suffix_start = suffix_pos;
                int suffix_end = suffix_pos + suffix.length();
                
                if (prefix_end <= suffix_start) {
                    string middle_part = s.substr(prefix_end, suffix_start - prefix_end);
                    
                    if (infix.empty() || middle_part.find(infix) != string::npos) {
                        min_length = min(min_length, suffix_end - prefix_pos);
                        break;
                    }
                }
            }
        }
        
        return min_length == INT_MAX ? -1 : min_length;
    }
};

class Solution:
    def shortestMatchingSubstring(self, s: str, p: str) -> int:
        def compute_lps(pattern):
            m = len(pattern)
            lps = [0] * m
            length = 0
            i = 1
            
            while i < m:
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps
        
        def find_occurrences(text, pattern):
            if not pattern:
                return list(range(len(text) + 1))
            
            lps = compute_lps(pattern)
            result = []
            i = j = 0
            n, m = len(text), len(pattern)
            
            while i < n:
                if text[i] == pattern[j]:
                    i += 1
                    j += 1
                
                if j == m:
                    result.append(i - j)
                    j = lps[j - 1]
                elif i < n and text[i] != pattern[j]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return result
        
        first_star = p.index('*')
        second_star = p.index('*', first_star + 1)
        
        prefix = p[:first_star]
        infix = p[first_star + 1:second_star]
        suffix = p[second_star + 1:]
        
        prefix_positions = find_occurrences(s, prefix)
        suffix_positions = find_occurrences(s, suffix)
        
        min_length = float('inf')
        
        for prefix_pos in prefix_positions:
            prefix_end = prefix_pos + len(prefix)
            
            for suffix_pos in suffix_positions:
                suffix_start = suffix_pos
                suffix_end = suffix_pos + len(suffix)
                
                if prefix_end <= suffix_start:
                    middle_part = s[prefix_end:suffix_start]
                    
                    if not infix or infix in middle_part:
                        min_length = min(min_length, suffix_end - prefix_pos)
                        break
        
        return min_length if min_length != float('inf') else -1

public class Solution {
    private int[] ComputeLPS(string pattern) {
        int m = pattern.Length;
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    private List<int> FindOccurrences(string text, string pattern) {
        List<int> result = new List<int>();
        if (string.IsNullOrEmpty(pattern)) {
            for (int k = 0; k <= text.Length; k++) {
                result.Add(k);
            }
            return result;
        }
        
        int[] lps = ComputeLPS(pattern);
        int i = 0, j = 0;
        int n = text.Length, m = pattern.Length;
        
        while (i < n) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
            }
            
            if (j == m) {
                result.Add(i - j);
                j = lps[j - 1];
            } else if (i < n && text[i] != pattern[j]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return result;
    }
    
    public int ShortestMatchingSubstring(string s, string p) {
        int firstStar = p.IndexOf('*');
        int secondStar = p.IndexOf('*', firstStar + 1);
        
        string prefix = p.Substring(0, firstStar);
        string infix = p.Substring(firstStar + 1, secondStar - firstStar - 1);
        string suffix = p.Substring(secondStar + 1);
        
        List<int> prefixPositions = FindOccurrences(s, prefix);
        List<int> suffixPositions = FindOccurrences(s, suffix);
        
        int minLength = int.MaxValue;
        
        foreach (int prefixPos in prefixPositions) {
            int prefixEnd = prefixPos + prefix.Length;
            
            foreach (int suffixPos in suffixPositions) {
                int suffixStart = suffixPos;
                int suffixEnd = suffixPos + suffix.Length;
                
                if (prefixEnd <= suffixStart) {
                    string middlePart = s.Substring(prefixEnd, suffixStart - prefixEnd);
                    
                    if (string.IsNullOrEmpty(infix) || middlePart.Contains(infix)) {
                        minLength = Math.Min(minLength, suffixEnd - prefixPos);
                        break;
                    }
                }
            }
        }
        
        return minLength == int.MaxValue ? -1 : minLength;
    }
}

/**
 * @param {string} s
 * @param {string} p
 * @return {number}
 */
var shortestMatchingSubstring = function(s, p) {
    const stars = [];
    for (let i = 0; i < p.length; i++) {
        if (p[i] === '*') stars.push(i);
    }
    
    const prefix = p.substring(0, stars[0]);
    const middle = p.substring(stars[0] + 1, stars[1]);
    const suffix = p.substring(stars[1] + 1);
    
    let minLen = Infinity;
    
    for (let i = 0; i <= s.length - prefix.length; i++) {
        if (s.substring(i, i + prefix.length) !== prefix) continue;
        
        const start = i + prefix.length;
        
        for (let j = s.length - suffix.length; j >= start; j--) {
            if (s.substring(j, j + suffix.length) !== suffix) continue;
            
            const end = j;
            const between = s.substring(start, end);
            
            if (middle === "" || between.includes(middle)) {
                minLen = Math.min(minLen, j + suffix.length - i);
                break;
            }
        }
    }
    
    return minLen === Infinity ? -1 : minLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-