Bloomberg 面试题：实现 Wordle 猜词反馈逻辑

题目描述

实现 Wordle 游戏的核心反馈逻辑：给定目标单词和玩家猜测，返回 5 个符号构成的反馈字符串。

反馈规则：

• * 表示字母正确且位置正确（绿色）
• % 表示字母存在于目标词但位置不对（黄色）
• - 表示字母完全不存在（灰色）

示例

目标单词: "staff"

猜测1: "world" -> "-----"  (没有匹配的字母)
猜测2: "worms" -> "----%"  (s存在但位置不对)
猜测3: "fluff" -> "---**"  (最后两个f正确)
猜测4: "staff" -> "*****"  (完全正确)

解题难点

关键点是正确处理重复字母。例如目标词 "staff" 有两个 f：

• 如果猜 "fluff"，前两个 f 不匹配，后两个 f 完全匹配
• 如果猜 "fffff"，只有第4、5位是 *，其他都是 -

解题思路

采用两遍扫描策略：

1. 第一遍：先标记所有完全匹配（位置和字母都对）的位置为 *
2. 第二遍：对于未匹配的位置，检查字母是否在目标词的剩余位置出现

Python 实现

def get_wordle_feedback(target: str, guess: str) -> str:
    n = len(target)
    result = ['-'] * n
    target_chars = list(target)
    
    # 第一遍：标记完全匹配
    for i in range(n):
        if guess[i] == target[i]:
            result[i] = '*'
            target_chars[i] = None  # 标记已使用
    
    # 第二遍：标记存在但位置不对
    for i in range(n):
        if result[i] == '*':
            continue
        if guess[i] in target_chars:
            result[i] = '%'
            # 移除第一个匹配的字符，避免重复计算
            target_chars[target_chars.index(guess[i])] = None
    
    return ''.join(result)

测试用例

# 基本测试
assert get_wordle_feedback("staff", "world") == "-----"
assert get_wordle_feedback("staff", "worms") == "----%"
assert get_wordle_feedback("staff", "fluff") == "---**"
assert get_wordle_feedback("staff", "staff") == "*****"

# 重复字母测试
assert get_wordle_feedback("hello", "lllll") == "-%*--"
assert get_wordle_feedback("aabbb", "bbaaa") == "%%*%%"

复杂度分析

• 时间复杂度：O(n²)，其中 n=5。可优化到 O(n) 使用 Counter
• 空间复杂度：O(n)

优化版本（使用 Counter）

from collections import Counter

def get_wordle_feedback_optimized(target: str, guess: str) -> str:
    n = len(target)
    result = ['-'] * n
    remaining = Counter(target)
    
    # 第一遍：完全匹配
    for i in range(n):
        if guess[i] == target[i]:
            result[i] = '*'
            remaining[guess[i]] -= 1
    
    # 第二遍：存在但位置不对
    for i in range(n):
        if result[i] == '-' and remaining[guess[i]] > 0:
            result[i] = '%'
            remaining[guess[i]] -= 1
    
    return ''.join(result)

面试技巧

1. 先处理简单情况，再考虑重复字母
2. 两遍扫描的思路要清晰表达
3. 主动提供测试用例展示边界情况考虑

需要面试辅助服务？联系我们

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

需要面试真题？ 立刻联系微信 Coding0201，获得真题。