题目详细题解

问题理解

题目要求判断一个字符串 $s$ 是否与一个整数数组 $a$（模板）匹配。匹配的条件本质上是要求字符串中的字符与数组中的数值之间建立一一对应的关系：

• 相同的数值必须对应相同的字符
• 相同的字符必须对应相同的数值

这是一个典型的双射（bijection）问题。

解题思路

要验证这种一一对应关系，我们可以使用两个哈希表（字典）：

• 字典 $m_1$：记录字符 $s_i$ 对应哪个数值 $a_i$
• 字典 $m_2$：记录数值 $a_i$ 对应哪个字符 $s_i$

核心思想：同时维护两个方向的映射关系，确保每个字符唯一映射到一个数值，每个数值也唯一映射到一个字符。

算法步骤

1. 长度检查：如果 $|s| \neq n$，直接输出 "NO"。

2. 遍历检查：对于每个位置 $j$（$0 \le j < n$）：

   • 取出当前字符 $s_j$ 和当前数值 $a_j$

   • 情况一：字符 $s_j$ 和数值 $a_j$ 都尚未建立映射

     • 建立双向映射：$m_1[s_j] = a_j$，$m_2[a_j] = s_j$

   • 情况二：已有映射但出现冲突

     • 如果 $s_j$ 已经映射到某个数值，但该数值不是 $a_j$，则冲突
     • 如果 $a_j$ 已经映射到某个字符，但该字符不是 $s_j$，则冲突
     • 出现任何冲突，则答案为 "NO"

3. 完成遍历：如果没有冲突，则答案为 "YES"

示例分析

以示例中的第一个测试用例为例：

$a = [3, 5, 2, 1, 3]$，检查字符串 "abfda"

遍历过程：

• $j=0$：$s_0=\text{'a'}$，$a_0=3$ → 建立映射：$\text{'a'}\to 3$，$3\to\text{'a'}$
• $j=1$：$s_1=\text{'b'}$，$a_1=5$ → 建立映射：$\text{'b'}\to 5$，$5\to\text{'b'}$
• $j=2$：$s_2=\text{'f'}$，$a_2=2$ → 建立映射：$\text{'f'}\to 2$，$2\to\text{'f'}$
• $j=3$：$s_3=\text{'d'}$，$a_3=1$ → 建立映射：$\text{'d'}\to 1$，$1\to\text{'d'}$
• $j=4$：$s_4=\text{'a'}$，$a_4=3$ → 检查：$\text{'a'}$ 已映射到 $3$，$3$ 已映射到 $\text{'a'}$，匹配 ✓

输出 "YES"

检查 "afbfa"：

• $j=0$：$\text{'a'}\to 3$，$3\to\text{'a'}$
• $j=1$：$\text{'f'}\to 5$，$5\to\text{'f'}$
• $j=2$：$\text{'b'}\to 2$，$2\to\text{'b'}$
• $j=3$：$s_3=\text{'f'}$，$a_3=1$ → 冲突：$\text{'f'}$ 已映射到 $5$，但当前位置数值是 $1$，不匹配 ✗

输出 "NO"

复杂度分析

• 时间复杂度：$O(n + L)$，其中 $L$ 为所有字符串的总长度。每个字符串的每个字符只处理一次。
• 空间复杂度：$O(\min(n, 26))$，由于字符只有小写字母，映射表大小最多为 $26$。

注意事项

1. 数值 $a_i$ 的范围很大（$-10^9 \le a_i \le 10^9$），但数量有限，可以用字典存储。
2. 字符集只有 $26$ 个小写字母，因此 $m_1$ 最多有 $26$ 个键值对。
3. 必须同时维护两个方向的映射，仅检查一个方向是不够的。
4. 对于每个测试用例，处理每个字符串时都需要重新初始化两个空字典。

代码实现要点

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    
    for _ in range(m):
        m1 = {}  # 字符 -> 数值
        m2 = {}  # 数值 -> 字符
        s = input().strip()
        
        if len(s) != n:
            print("NO")
            continue
        
        ok = True
        for j in range(n):
            if s[j] not in m1 and a[j] not in m2:
                m1[s[j]] = a[j]
                m2[a[j]] = s[j]
            elif (s[j] in m1 and m1[s[j]] != a[j]) or \
                 (a[j] in m2 and m2[a[j]] != s[j]):
                ok = False
                break
        
        print("YES" if ok else "NO")