制造焦虑：打破幻觉
最近 Google 的一道字符串面试题在北美求职圈引发热议。
很多人第一眼看到题目：「不就是字符串匹配吗？Python 的 in 操作符秒了！」
大错特错。
这道题的核心在于转写映射（Transliteration）—— 一个字符可能映射成多个字符（如 æ → ae），这让普通的子串匹配完全失效。
我们 oavoservice 团队深入分析后发现，这道题考察的是 字符串预处理、双指针匹配 和 边界处理 的综合能力。
题目拆解：展示专业
🔍 原题描述
String Matching With Transliteration
You may or may not know that Google Docs has a feature to find and replace even for characters not in the standard English alphabet ([A-Z]).
To do this, we first need a transliteration map:
tl_map = {
"ë": "e",
"é": "e",
"û": "u",
"æ": "ae",
"ž": "zed",
# ...
}
Given a haystack string, a needle string, and the transliteration mapping, return whether the needle is matched within the haystack.
📝 中文翻译
Google Docs 有一个功能：即使是非标准英文字母（如带重音符号的字符），也能进行查找和替换。
为了实现这个功能，我们需要一个转写映射表，将非标准字符转换为标准英文字符串。
给定：
haystack：被搜索的字符串needle：要查找的模式串tl_map：转写映射表
问题：判断 needle（转写后）是否是 haystack（转写后）的子串。
🎯 示例分析
Example 1:
haystack: "I love crème brûlée"
needle: "eme"
return: True
解释：
- "crème" 中的 "è" 转写为 "e"
- "crème" → "creme"
- "eme" 是 "creme" 的子串 ✓
Example 2:
haystack: "I love crème brûlée"
needle: "ême"
return: True
解释：
- needle "ême" 中的 "ê" 转写为 "e"
- needle → "eme"
- haystack 中 "crème" → "creme"
- "eme" 是 "creme" 的子串 ✓
Example 3:
haystack: "Ole Gunnar Solskjær is amazing"
needle: "Solskja"
return: True
解释：
- "Solskjær" 中的 "æ" 转写为 "ae"
- "Solskjær" → "Solskjaer"
- "Solskja" 是 "Solskjaer" 的前缀 ✓
Example 4: ⚠️ 关键陷阱
haystack: "Ole Gunnar Solskjær is amazing"
needle: "Solskjear"
return: False
解释：
- "Solskjær" → "Solskjaer"
- "Solskjear" ≠ "Solskjaer"（e 和 a 的位置不同）
- 注意：needle 中的 "ea" 不等于 "æ" 的转写 "ae" ✗
深度复盘：建立信任
🧠 题目本质分析
这道题的难点在于：
| 考点 | 具体内容 |
|---|---|
| 一对多映射 | 一个字符可能映射成多个字符（æ → ae） |
| 双向转写 | haystack 和 needle 都需要转写 |
| 长度变化 | 转写后字符串长度会变化 |
| 边界处理 | 部分匹配、跨字符匹配 |
📊 关键洞察
方法一：预处理转写
最直观的方法：先把 haystack 和 needle 都转写成标准英文，再做子串匹配。
haystack: "crème" → "creme"
needle: "ême" → "eme"
匹配: "eme" in "creme" → True
方法二：边匹配边转写
不预处理，在匹配过程中按需展开字符。适用于超长字符串场景。
方案引入：核心算法
解法一：预处理 + 子串匹配（推荐）
def transliterate(s: str, tl_map: dict) -> str:
"""
将字符串中的非标准字符转写为标准英文
Args:
s: 原始字符串
tl_map: 转写映射表
Returns:
转写后的字符串
"""
result = []
for char in s:
if char in tl_map:
result.append(tl_map[char])
else:
result.append(char)
return ''.join(result)
def string_match_with_transliteration(haystack: str, needle: str, tl_map: dict) -> bool:
"""
Google 面试真题：字符串转写匹配
Args:
haystack: 被搜索的字符串
needle: 要查找的模式串
tl_map: 转写映射表
Returns:
bool: needle（转写后）是否是 haystack（转写后）的子串
"""
# Step 1: 转写两个字符串
trans_haystack = transliterate(haystack, tl_map)
trans_needle = transliterate(needle, tl_map)
# Step 2: 子串匹配
return trans_needle in trans_haystack
🧪 测试用例
tl_map = {
"ë": "e",
"é": "e",
"è": "e",
"ê": "e",
"û": "u",
"ù": "u",
"æ": "ae",
"ž": "zed",
}
# Test 1: 基本匹配
print(string_match_with_transliteration(
"I love crème brûlée", "eme", tl_map
)) # Expected: True
# Test 2: needle 也需要转写
print(string_match_with_transliteration(
"I love crème brûlée", "ême", tl_map
)) # Expected: True
# Test 3: 一对多映射
print(string_match_with_transliteration(
"Ole Gunnar Solskjær is amazing", "Solskja", tl_map
)) # Expected: True
# Test 4: 关键陷阱 - 顺序错误
print(string_match_with_transliteration(
"Ole Gunnar Solskjær is amazing", "Solskjear", tl_map
)) # Expected: False
# Test 5: 完整匹配
print(string_match_with_transliteration(
"Ole Gunnar Solskjær is amazing", "Solskjaer", tl_map
)) # Expected: True
# Test 6: 空 needle
print(string_match_with_transliteration(
"Hello World", "", tl_map
)) # Expected: True
# Test 7: 无特殊字符
print(string_match_with_transliteration(
"Hello World", "World", tl_map
)) # Expected: True
# Test 8: 多字符映射
print(string_match_with_transliteration(
"ženeva", "zed", tl_map
)) # Expected: True
解法二：边匹配边转写（优化内存）
当 haystack 非常长时，预处理会占用大量内存。可以采用「懒展开」策略：
def lazy_match(haystack: str, needle: str, tl_map: dict) -> bool:
"""
懒展开匹配：不预处理整个字符串
适用于超长 haystack 场景
"""
# 先转写 needle（通常较短）
trans_needle = transliterate(needle, tl_map)
if not trans_needle:
return True
# 生成器：逐字符展开 haystack
def expand_haystack():
for char in haystack:
expanded = tl_map.get(char, char)
for c in expanded:
yield c
# 滑动窗口匹配
needle_len = len(trans_needle)
window = []
for char in expand_haystack():
window.append(char)
if len(window) > needle_len:
window.pop(0)
if len(window) == needle_len and ''.join(window) == trans_needle:
return True
return False
解法三：KMP 优化（面试加分项）
如果面试官追问「如何优化时间复杂度」，可以提及 KMP 算法：
def kmp_match(haystack: str, needle: str, tl_map: dict) -> bool:
"""
KMP 优化版本
时间复杂度: O(n + m)，其中 n = len(haystack), m = len(needle)
"""
trans_haystack = transliterate(haystack, tl_map)
trans_needle = transliterate(needle, tl_map)
if not trans_needle:
return True
# 构建 KMP 失败函数
def build_failure(pattern):
m = len(pattern)
failure = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = failure[j - 1]
if pattern[i] == pattern[j]:
j += 1
failure[i] = j
return failure
failure = build_failure(trans_needle)
# KMP 匹配
j = 0
for i, char in enumerate(trans_haystack):
while j > 0 and char != trans_needle[j]:
j = failure[j - 1]
if char == trans_needle[j]:
j += 1
if j == len(trans_needle):
return True
return False
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
预处理 + in |
O(n × m) | O(n + m) | 一般情况 |
| 懒展开匹配 | O(n × m) | O(m) | 超长 haystack |
| KMP 优化 | O(n + m) | O(n + m) | 高性能要求 |
其中：n = len(haystack)，m = len(needle)
🤯 面试官的 Followup 陷阱
Followup 1: 如果映射是双向的怎么办？
问题：不仅 æ → ae，还有 ae → æ？
答案：需要构建等价类，将所有等价的表示归一化。
def normalize(s: str, equivalences: list) -> str:
"""
归一化：将所有等价表示转为统一形式
equivalences: [("æ", "ae"), ("ë", "e"), ...]
"""
for orig, replacement in equivalences:
s = s.replace(orig, replacement)
return s
Followup 2: 如果要返回所有匹配位置呢？
def find_all_matches(haystack: str, needle: str, tl_map: dict) -> list:
"""返回所有匹配的起始位置（在原始 haystack 中）"""
trans_haystack = transliterate(haystack, tl_map)
trans_needle = transliterate(needle, tl_map)
# 建立转写后位置到原始位置的映射
pos_map = [] # pos_map[i] = 转写后第 i 个字符对应原始字符串的位置
for i, char in enumerate(haystack):
expanded = tl_map.get(char, char)
for _ in expanded:
pos_map.append(i)
# 查找所有匹配
results = []
start = 0
while True:
idx = trans_haystack.find(trans_needle, start)
if idx == -1:
break
results.append(pos_map[idx]) # 转换回原始位置
start = idx + 1
return results
Followup 3: 如果要支持大小写不敏感匹配？
def case_insensitive_match(haystack: str, needle: str, tl_map: dict) -> bool:
"""大小写不敏感的转写匹配"""
# 将映射表也扩展为大小写不敏感
extended_map = {}
for k, v in tl_map.items():
extended_map[k.lower()] = v.lower()
extended_map[k.upper()] = v.upper()
return string_match_with_transliteration(
haystack.lower(),
needle.lower(),
extended_map
)
Followup 4: 如何处理 Unicode 组合字符？
问题：é 可能是单个字符 \u00e9，也可能是 e + \u0301（组合重音符号）。
答案：使用 Unicode 正规化（NFC/NFD）。
import unicodedata
def normalize_unicode(s: str) -> str:
"""Unicode 正规化：将组合字符转为预组合形式"""
return unicodedata.normalize('NFC', s)
def match_with_unicode_normalization(haystack: str, needle: str, tl_map: dict) -> bool:
"""先正规化再匹配"""
haystack = normalize_unicode(haystack)
needle = normalize_unicode(needle)
return string_match_with_transliteration(haystack, needle, tl_map)
🔥 为什么大多数人会挂？
| 常见错误 | 正确做法 |
|---|---|
| 只转写 haystack | haystack 和 needle 都要转写 |
| 忽略一对多映射 | æ → ae 会改变字符串长度 |
用 replace 链式调用 |
可能导致重复替换，应逐字符处理 |
| 忘记空字符串检查 | needle 为空应返回 True |
| 位置映射错误 | 返回位置时要映射回原始字符串 |
代码模板（可直接使用）
def transliterate(s: str, tl_map: dict) -> str:
"""转写字符串"""
return ''.join(tl_map.get(c, c) for c in s)
def match_with_transliteration(haystack: str, needle: str, tl_map: dict) -> bool:
"""
Google 面试真题：字符串转写匹配
"""
return transliterate(needle, tl_map) in transliterate(haystack, tl_map)
📞 oavoservice 服务
这种字符串处理 + 映射转换的题目，是 Google 面试的经典风格。
如果你在面试中遇到类似题目，我们可以提供：
- ✅ OA代写：CodeSignal / HackerRank 满分保障
- ✅ VO辅助：Live Coding 实时场外助攻
- ✅ Followup 准备：帮你预判面试官的 Unicode、位置映射等追问
👉 立即添加微信：Coding0201
不要让一道字符串转写题，毁掉你的 Google Offer。
本文由 oavoservice 团队原创，转载请注明出处。