GFG编程题：判断Needle是否为Haystack的乱序子串及代码问题

你的代码目前的问题在于错误地检查了整个haystack的字符频率，而不是检查haystack中是否存在一个长度与needle相等的连续子串，其字符频率与needle完全匹配。举个实际的反例：如果needle是"abc"，haystack是"abbc"，你的代码会因为haystack整体包含a:1、b:2、c:1，满足needle的字符数量要求，错误返回True；但实际上haystack里没有长度为3的子串同时包含a、b、c各一个，正确结果应该是False。

正确的思路 #

我们需要用滑动窗口的方式，在haystack中遍历所有长度等于needle的子串，检查每个子串的字符频率是否和needle完全一致：

1. 先处理边界情况：如果needle长度大于haystack，直接返回False。
2. 计算needle的字符频率字典。
3. 在haystack中滑动一个长度为len(needle)的窗口：
   • 计算初始窗口的字符频率，对比是否匹配needle的频率。
   • 之后每次滑动窗口时，只更新边界字符的频率（移除窗口左侧字符，添加右侧新字符），再进行对比。
4. 遍历完所有窗口都无匹配则返回False。

修正后的代码 #

from collections import defaultdict

def isShuffledSubstring(needle, haystack):
    needle_len = len(needle)
    haystack_len = len(haystack)
    
    # 边界判断：needle更长直接返回False
    if needle_len > haystack_len:
        return False
    
    # 统计needle的字符频率
    needle_freq = defaultdict(int)
    for char in needle:
        needle_freq[char] += 1
    
    # 初始化第一个窗口的字符频率
    window_freq = defaultdict(int)
    for i in range(needle_len):
        window_freq[haystack[i]] += 1
    
    # 检查第一个窗口
    if window_freq == needle_freq:
        return True
    
    # 滑动窗口遍历剩余部分
    for i in range(needle_len, haystack_len):
        # 移除窗口左侧的字符
        left_char = haystack[i - needle_len]
        window_freq[left_char] -= 1
        if window_freq[left_char] == 0:
            del window_freq[left_char]  # 删除计数为0的键，避免干扰字典对比
        
        # 添加窗口右侧的新字符
        right_char = haystack[i]
        window_freq[right_char] += 1
        
        # 对比当前窗口与needle的频率
        if window_freq == needle_freq:
            return True
    
    # 所有窗口都不匹配
    return False

代码说明 #

• 用defaultdict简化字符频率统计，也可以替换成你原来的普通字典写法，逻辑一致。
• 滑动窗口的优化：每次只更新边界字符的频率，时间复杂度从O(n*m)降到O(n)（n为haystack长度，m为needle长度），效率更高，适配题目给出的长度约束（最长1000）。
• 移除左侧字符后，若计数变为0则删除该键，确保字典对比时不会因为存在无效键而出现错误匹配。

测试验证 #

几个关键测试用例：

• 测试用例1：Needle="abc"，Haystack="cbabadcbbabbcbabaabccbabc" → 返回True（存在可重排为abc的子串）
• 测试用例2：Needle="abc"，Haystack="abbc" → 返回False（无符合要求的子串）
• 测试用例3：Needle="aab"，Haystack="abac" → 返回True（子串"aba"可重排为aab）

这些用例你的原代码会处理错误，修正后的代码能正确返回结果。

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