写点什么

【LeetCode】亲密字符串 Java 题解

作者:HQ数字卡
  • 2021 年 12 月 03 日
  • 本文字数:1188 字

    阅读完需:约 4 分钟

题目描述

给你两个字符串 s 和 goal ,只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果,就返回 true ;否则返回 false 。


交换字母的定义是:取两个下标 i 和 j (下标从 0 开始)且满足 i != j ,接着交换 s[i] 和 s[j] 处的字符。


例如,在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。


示例 1:
输入:s = "ab", goal = "ba"输出:true解释:你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba",此时 s 和 goal 相等。
示例 2:
输入:s = "ab", goal = "ab"输出:false解释:你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba",此时 s 和 goal 不相等。
示例 3:
输入:s = "aa", goal = "aa"输出:true解释:你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa",此时 s 和 goal 相等。
示例 4:
输入:s = "aaaaaaabc", goal = "aaaaaaacb"输出:true
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/buddy-strings著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法每日一题是字符串处理题目。根据题目描述,我们可以通过交换 s 中的两个字母得到与 goal 相等的结果,这一关键点,进行分情况讨论。

  • 首先,我们分别获取 s, goal 的长度,当长度不相等时候,直接返回 false。

  • 当两者长度相同的时候。分情况讨论,当 s 与 goal 相同时候,只需保证 s 中有两个相同的字符即可。当 s 与 goal 不同时候,需要记录不同的位置,并交换比较。实现代码如下:

通过代码

class Solution {    public boolean buddyStrings(String s, String goal) {        int n = s.length();        int m = goal.length();
if (n != m) { return false; }
if (s.equals(goal)) { int[] count = new int[26]; for (int i = 0; i < n; i++) { count[s.charAt(i) - 'a']++; if (count[s.charAt(i) - 'a'] >= 2) { return true; } } return false; } else { int first = -1, second = -1; for (int i = 0; i < m; i++) { if (s.charAt(i) != goal.charAt(i)) { if (first == -1) first = i; else if (second == -1) second = i; else return false; } } return (second != -1 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first));
} }}
复制代码

总结

  • 上述代码的时间复杂度是 O(n),空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 47 分钟前阅读数: 4
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】亲密字符串Java题解