hiho一下第284周《MSFT》题目分析

5
2

如果字符串中没有重复的字符,那么这题就是一道经典题。 我们只需要找轮换即可。

比如第一个样例

msra
asmr

只有有轮换m->a->r->m。 答案就是长度-1 = 2。

对于有重复的情况,难点本质在于S中的一个字符匹配T中哪个字符不确定。由于最多有4个字符出现2次,所以我们可以枚举重复字符的匹配关系。

比如对于第二个样例:

fsmambfcs
mfsmbfcsa

我们不妨对S中重复的字符进行区分,先出现的保持小写,后出现的用大写字母: fsmambfcs -> fsmaMbFcS

而T中每个重复出现的字符都可能有2种匹配情况,一共有8种情况: mfsmbfcsa

mfsMbFcSa
mfSMbFcsa
mFsMbfcSa
mFSMbfcsa
MfsmbFcSa
MfSmbFcsa
MFsmbfcSa
MFSmbfcsa

我们用 fsmaMbFcS 与上述每一个进行求解最少交换次数。再从中找最少的即可。

1 answer(s)

2

能解释一下轮换吗 百度出来的 和本题不太相关

write answer 切换为英文 切换为中文


转发分享