LeetCode 2840. 判断通过操作能否让字符串相等2 超详细题解

LeetCode 2840. 判断通过操作能否让字符串相等2 超详细题解️ 标签LeetCode、算法、字符串、贪心、哈希、Python题目难度中等核心考点字符串交换规则、奇偶下标分组、字符统计一、题目重现题目描述给定两个字符串s1和s2两个字符串长度都为n且只包含小写英文字母。你可以对两个字符串中的任意一个执行以下操作任意次选择两个下标i和j满足i j且j - i是偶数然后交换这个字符串中两个下标对应的字符。如果你可以让字符串s1和s2相等返回true否则返回false。示例 1输入s1 abcdba, s2 cabdab 输出true 解释 - 选择下标 i0j2得到 s1 cbadba - 选择下标 i2j4得到 s1 cbbdaa - 选择下标 i1j5得到 s1 cabdab s2示例 2输入s1 abe, s2 bea 输出false 解释无法通过合法操作让两个字符串相等提示n s1.length s2.length1 n 10⁵s1 和 s2 只包含小写英文字母二、题意深度解析2.1 操作规则拆解题目允许的交换条件两个下标之差为偶数。我们先推导这条规则背后的本质若j - i是偶数说明i和j的奇偶性相同。偶数 - 偶数 偶数奇数 - 奇数 偶数奇数 - 偶数 奇数也就是说只能交换同奇偶下标的字符不同奇偶下标的字符永远无法交换。2.2 核心结论核心规律字符串里偶数下标位置的字符可以在所有偶数下标之间任意交换字符串里奇数下标位置的字符可以在所有奇数下标之间任意交换偶数下标和奇数下标之间的字符永远不能互换基于这个结论判断条件就变得非常清晰把 s1 的偶数下标字符、奇数下标字符分开统计把 s2 的偶数下标字符、奇数下标字符分开统计如果 s1 和 s2 的偶数分组字符完全一致奇数分组字符也完全一致就返回true否则false三、解题思路3.1 思路步骤分别遍历两个字符串按下标奇偶性把字符分到对应的组里对每个分组的字符进行排序排序后对比能快速判断字符种类和数量是否一致对比 s1 偶数分组和 s2 偶数分组是否相同对比 s1 奇数分组和 s2 奇数分组是否相同两组都一致返回true否则false3.2 复杂度分析时间复杂度O(n log n)遍历字符串O(n)分组排序O(n log n)能轻松通过1e5的数据量空间复杂度O(n)存储分组后的字符优化也可以用数组统计26个字母出现次数空间复杂度降为O(1)更适合超大数据量代码也会更简洁。四、完整代码实现解法一分组排序对比直观易懂classSolution:defcheckStrings(self,s1:str,s2:str)-bool:# 分别存放s1的偶、奇数下标字符s1_even[]s1_odd[]# 分别存放s2的偶、奇数下标字符s2_even[]s2_odd[]# 遍历字符串按下标奇偶分组foridx,chinenumerate(s1):ifidx%20:s1_even.append(ch)else:s1_odd.append(ch)foridx,chinenumerate(s2):ifidx%20:s2_even.append(ch)else:s2_odd.append(ch)# 排序后对比种类和数量一致则相等returnsorted(s1_even)sorted(s2_even)andsorted(s1_odd)sorted(s2_odd)解法二计数法空间O(1)效率更高针对1e5数据量用数组统计字符出现次数不排序效率更优。classSolution:defcheckStrings(self,s1:str,s2:str)-bool:# 统计偶数下标、奇数下标字符次数26个小写字母cnt1_even[0]*26cnt1_odd[0]*26cnt2_even[0]*26cnt2_odd[0]*26foriinrange(len(s1)):# s1字符计数c1ord(s1[i])-ord(a)ifi%20:cnt1_even[c1]1else:cnt1_odd[c1]1# s2字符计数c2ord(s2[i])-ord(a)ifi%20:cnt2_even[c2]1else:cnt2_odd[c2]1# 计数完全一致则返回Truereturncnt1_evencnt2_evenandcnt1_oddcnt2_odd五、代码讲解解法一详细说明初始化四个空列表存放两个字符串的奇偶下标字符用enumerate遍历字符串拿到下标和字符按下标奇偶性放入对应列表对列表排序排序后如果两个列表元素一样说明字符种类和数量完全相同可以通过交换达到一致只有偶数组合、奇数组合都匹配才返回True解法二详细说明用4个长度为26的数组对应26个小写英文字母统计出现次数遍历字符串将字符转为0-25的数字对应下标计数直接对比计数数组不用排序时间开销更小空间固定为O(1)适合大数据量场景工业级代码推荐用这种写法六、测试验证测试示例1s1abcdbas2cabdab# 运行代码solSolution()print(sol.checkStrings(s1,s2))# 输出 True测试示例2s1abes2bea# 运行代码solSolution()print(sol.checkStrings(s1,s2))# 输出 False七、常见误区误区以为能任意交换字符直接判断两个字符串字符是否一致错误原因忽略了交换规则奇偶下标字符不能互换例子s1abes2bea整体字符一致但奇偶分组不同所以返回false误区只对比偶数分组不对比奇数分组错误原因必须两组都完全匹配才能通过交换让两个字符串相等八、总结这道题看似是字符串操作题实则是规律推导题。只要看透“只能交换同奇偶下标字符”这个核心题目就变得非常简单。做题技巧遇到带交换规则的字符串题先推导交换的本质限制再根据限制设计判断逻辑不要盲目模拟交换模拟交换会超时尤其数据量大时。推荐优先使用计数法效率更高代码简洁适合笔试、面试场景。 博主寄语持续更新力扣题解、算法实战、编程技巧主打通俗易懂、干货满满。欢迎点赞、收藏、关注有疑问可以在评论区交流。