#P4244. 第2题-凯撒密码
-
ID: 3320
Tried: 4
Accepted: 2
Difficulty: 5
所属公司 :
京东
时间 :2025年10月18日
-
算法标签>哈希表字符串
第2题-凯撒密码
解题思路
-
本题要求:给定整数数组
a
与若干字符串s
,判断s
能否与a
建立一一对应(双射) 的位置映射:相同数字对应相同字符,且相同字符对应相同数字,并且长度相等。 -
核心做法:把序列按首次出现顺序压缩成模式串。
- 对数组
a
:从左到右,第一次见到某个值就分配一个新的编号0,1,2,...
,形成模式序列patA
。 - 对任意待判字符串
s
:同样按字符的首次出现分配编号,得到patS
。 - 若
|s| != n
直接否;否则比较patS
与patA
是否完全相同,相同则存在双射,对应输出YES
,否则NO
。
- 对数组
-
该方法天然保证了“双向一致”:
- 相同数字得到相同编号 ⇒ 必有相同字符;
- 相同字符得到相同编号 ⇒ 必有相同数字; 两个模式完全一致即等价于存在一一映射。
复杂度分析
- 预处理数组
a
生成patA
:O(n)
。 - 对每个字符串
s
生成patS
并比较:O(|s|)
。 - 若所有测试中
Σn
与Σ|s|
不超过2e5
(题面给定),总时间O(Σn + Σ|s|)
,空间O(n + |s|max)
,满足要求。
代码实现
Python
import sys
# 将序列按首次出现顺序映射成模式编号序列
def build_pattern_from_array(arr):
mp = {} # 值 -> 首次出现编号
nxt = 0
pat = []
for v in arr:
if v not in mp:
mp[v] = nxt
nxt += 1
pat.append(mp[v])
return pat
def build_pattern_from_string(s):
mp = {} # 字符 -> 首次出现编号
nxt = 0
pat = []
for ch in s:
if ch not in mp:
mp[ch] = nxt
nxt += 1
pat.append(mp[ch])
return pat
def main():
data = sys.stdin.read().strip().split()
it = iter(data)
t = int(next(it))
out = []
for _ in range(t):
n = int(next(it))
arr = [int(next(it)) for _ in range(n)]
base = build_pattern_from_array(arr)
m = int(next(it))
for _ in range(m):
s = next(it)
if len(s) != n:
out.append("NO")
else:
out.append("YES" if build_pattern_from_string(s) == base else "NO")
print("\n".join(out))
if __name__ == "__main__":
main()
Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
// 将整型数组按首次出现顺序压缩为模式
static int[] patternFromArray(int[] a) {
Map<Integer, Integer> mp = new HashMap<>();
int n = a.length, nxt = 0;
int[] pat = new int[n];
for (int i = 0; i < n; i++) {
Integer v = a[i];
if (!mp.containsKey(v)) mp.put(v, nxt++);
pat[i] = mp.get(v);
}
return pat;
}
// 将字符串按首次出现顺序压缩为模式
static int[] patternFromString(String s) {
Map<Character, Integer> mp = new HashMap<>();
int n = s.length(), nxt = 0;
int[] pat = new int[n];
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (!mp.containsKey(c)) mp.put(c, nxt++);
pat[i] = mp.get(c);
}
return pat;
}
// 比较两个整型模式是否相同
static boolean equalPattern(int[] a, int[] b) {
if (a.length != b.length) return false;
for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return false;
return true;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int t = Integer.parseInt(br.readLine().trim());
StringBuilder ans = new StringBuilder();
for (int cas = 0; cas < t; cas++) {
int n = Integer.parseInt(br.readLine().trim());
st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
int[] base = patternFromArray(arr);
int m = Integer.parseInt(br.readLine().trim());
for (int i = 0; i < m; i++) {
String s = br.readLine().trim();
if (s.length() != n) {
ans.append("NO\n");
} else {
int[] pat = patternFromString(s);
ans.append(equalPattern(base, pat) ? "YES\n" : "NO\n");
}
}
}
System.out.print(ans.toString());
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 将整型数组按首次出现顺序压缩为模式
vector<int> patternFromArray(const vector<long long>& a) {
unordered_map<long long,int> mp; // 值 -> 首次编号
vector<int> pat; pat.reserve(a.size());
int nxt = 0;
for (auto v : a) {
if (!mp.count(v)) mp[v] = nxt++;
pat.push_back(mp[v]);
}
return pat;
}
// 将字符串按首次出现顺序压缩为模式
vector<int> patternFromString(const string& s) {
// 由于题中是小写字母,也可用数组;这里用 map 写法统一
int n = (int)s.size();
vector<int> pat; pat.reserve(n);
vector<int> pos(256, -1); // 字符 -> 首次编号,-1 表示未出现
int nxt = 0;
for (char c : s) {
unsigned char uc = (unsigned char)c;
if (pos[uc] == -1) pos[uc] = nxt++;
pat.push_back(pos[uc]);
}
return pat;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
if (!(cin >> t)) return 0;
while (t--) {
int n; cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> base = patternFromArray(a);
int m; cin >> m;
for (int i = 0; i < m; ++i) {
string s; cin >> s;
if ((int)s.size() != n) {
cout << "NO\n";
continue;
}
vector<int> pat = patternFromString(s);
cout << (pat == base ? "YES\n" : "NO\n");
}
}
return 0;
}
题目内容
小Q在路上捡到了一张字条,上面写了一个数组 a 。小Q猜测这些数字可能是某种凯撒密码,于是他找来了一堆字符串,请你判断他找来的字符串能否匹配字条上的数字模板?
当字符串 s 同时满足以下所有条件时,视为匹配模板:
-
字符串 s 的长度等于数组 a 的元素数量。
-
数组 a 中相同的数字对应字符串 s 中相同的字符。即,若 ai=aj ,则 si=sj(1<=i,j<=n)
-
字符串 s 中相同的字符对应数组 a 中相同的数字。即,若 si=sj,则 ai=aj(1≤i,j≤n).
换句话说,字符串的字符与数组元素之间必须存在对应关系。
例如,若 a=[3,5,2,1,3],则字符串“abfda”匹配模板,而“afbfa”不匹配,因为字符“f” 对应数字 1 和 5 .
输入描述
单个测试用例包含多组数据,第一行输入一个整数 t(1<=t<=105) ,表示数据的数量.对于每组数据:
第一行包含一个整数 n(1<=n<=2•105),表示数组 a 的元素数量.
第二行包含恰好 n 个整数ai(−109≤ai≤109) 表示数组 a 的元素。
第三行包含一个整数 m(1≤m≤2•105),表示需要检查的字符串数量。
接下来 m 行,每行包含一个非空字符串 sj(1≤∣sj∣≤2•105) ,由小写字母组成。
保证所有测试用例的 n 之和不超过 2•105,所有字符串长度之和不超过 2•105 .
输出描述
每个测试用例输出 m 行。如果第 1 个字符串匹配模板,第 i 行输出 YES ,否则输出 NO (注意输出为大写)。
样例1
**输入
3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb
输出
YES
NO
YES
NO
NO
NO
YES
NO
YES