本题要求:给定整数数组 a 与若干字符串 s,判断 s 能否与 a 建立一一对应(双射) 的位置映射:相同数字对应相同字符,且相同字符对应相同数字,并且长度相等。
核心做法:把序列按首次出现顺序压缩成模式串。
a:从左到右,第一次见到某个值就分配一个新的编号 0,1,2,...,形成模式序列 patA。s:同样按字符的首次出现分配编号,得到 patS。|s| != n 直接否;否则比较 patS 与 patA 是否完全相同,相同则存在双射,对应输出 YES,否则 NO。该方法天然保证了“双向一致”:
考古学家发现了一块远古石板,上面刻有一串整数印记。他们猜测每个数字都对应一个符文(小写字母)。为了破译,你需要判断一些候选符文串是否与石板的印记模板相符。
一个印记序列由 n 个整数 d1,d2,...,dn 描述。一个候选符文串 S=s1s2...sm 由小写字母组成。我们称 S 匹配该印记序列,当且仅当同时满足:
现在给出多个测试用例,每个用例包含一个印记序列和若干候选符文串。请对每个符文串判断是否匹配。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册