Scala：求解给定文本中多目标词间的最小绝对距离

针对你提出的需求——找出给定文本中包含所有目标词的子序列里，最左和最右目标词的最小位置跨度，我整理了一套清晰的实现方案，结合你的MinKWin思路展开：

问题明确 #

我们的核心目标是：在文本中找到同时包含所有目标词的最短区间，这个区间的长度定义为区间内第一个目标词和最后一个目标词的位置差（绝对距离）。比如你给出的示例：

文本：" a b cat dog x y z n m p fox x dog b b cat "
目标词：fox, dog, cat
最终最小距离为14（fox在位置24，cat在位置38，38-24=14）

算法核心思路 #

这个问题可以用**滑动窗口（双指针）**的思路高效解决，步骤如下：

• 第一步：遍历文本，记录每个目标词出现的所有起始位置。比如示例中：
  • cat的位置：[4, 38]
  • dog的位置：[8, 30]
  • fox的位置：[24]
• 第二步：把所有目标词的位置信息合并成一个按位置从小到大排序的列表，每个元素是（位置, 对应词）的元组，得到：
  [(4, 'cat'), (8, 'dog'), (24, 'fox'), (30, 'dog'), (38, 'cat')]
• 第三步：用滑动窗口遍历这个排序后的列表，维护一个包含所有目标词的窗口，不断缩小左边界来找到最短的有效窗口，计算窗口首尾的位置差，更新最小距离。

示例验证过程 #

我们用你的示例走一遍算法：

1. 排序后的位置列表如上，初始左指针在0位置
2. 移动右指针到索引2（对应fox的位置24），此时窗口包含cat、dog、fox，满足条件，计算距离24-4=20，这是当前最小距离
3. 继续移动右指针到索引3（dog的位置30），窗口仍满足条件，但距离30-4=26，比20大，不更新
4. 右指针到索引4（cat的位置38），窗口满足条件，开始尝试缩小左边界：
   • 左指针移到索引1（dog的位置8），窗口仍包含所有目标词，距离38-8=30，还是比20大
   • 左指针移到索引2（fox的位置24），窗口包含fox、dog、cat，距离38-24=14，这是更小的值，更新最小距离为14
5. 最终得到最小距离14，和预期一致

代码实现（Python） #

下面是可直接运行的代码，已经适配了你的示例场景：

def find_min_target_distance(text, target_words):
    # 先拆分文本，记录每个目标词的起始位置
    word_positions = {}
    current_idx = 0
    words = text.split()
    
    for word in words:
        # 找到当前单词在文本中的起始位置
        start_pos = text.find(word, current_idx)
        if word in target_words:
            if word not in word_positions:
                word_positions[word] = []
            word_positions[word].append(start_pos)
        # 更新当前索引到单词末尾，避免重复查找
        current_idx = start_pos + len(word)
    
    # 合并并排序所有目标词的位置信息
    sorted_positions = []
    for word, positions in word_positions.items():
        for pos in positions:
            sorted_positions.append((pos, word))
    sorted_positions.sort(key=lambda x: x[0])
    
    # 滑动窗口寻找最小距离
    from collections import defaultdict
    window_word_count = defaultdict(int)
    left_ptr = 0
    min_distance = float('inf')
    required_words = len(target_words)
    formed_words = 0
    
    for right_ptr in range(len(sorted_positions)):
        current_word = sorted_positions[right_ptr][1]
        window_word_count[current_word] += 1
        
        # 当该词首次加入窗口时，计数formed_words
        if window_word_count[current_word] == 1:
            formed_words += 1
        
        # 窗口包含所有目标词时，尝试缩小左边界
        while formed_words == required_words:
            current_window_dist = sorted_positions[right_ptr][0] - sorted_positions[left_ptr][0]
            if current_window_dist < min_distance:
                min_distance = current_window_dist
            
            # 移动左指针，更新窗口内的词计数
            left_word = sorted_positions[left_ptr][1]
            window_word_count[left_word] -= 1
            if window_word_count[left_word] == 0:
                formed_words -= 1
            left_ptr += 1
    
    # 如果没找到包含所有目标词的区间，返回-1
    return min_distance if min_distance != float('inf') else -1

# 测试示例
sample_text = " a b cat dog x y z n m p fox x dog b b cat "
targets = {"fox", "dog", "cat"}
print(find_min_target_distance(sample_text, targets))  # 输出14

这个算法的时间复杂度主要由排序步骤决定，是O(N log N)，其中N是目标词出现的总次数，效率很高，适合处理较长的文本。

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