859. 亲密字符串 : 简单字符串模拟题

简介: 859. 亲密字符串 : 简单字符串模拟题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 859. 亲密字符串 ,难度为 简单


Tag : 「模拟」


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


交换字母的定义是:取两个下标 ij (下标从 00 开始)且满足 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
复制代码


提示:


  • 1 <= s.length, goal.length <= 2 * 10^41<=s.length,goal.length<=2104
  • sgoal 由小写英文字母组成


模拟



根据题意进行模拟即可,搞清楚什么情况下两者为「亲密字符」:


  1. ssgoalgoal 长度 或 词频不同,必然不为亲密字符;
  2. 当「ssgoalgoal 不同的字符数量为 22(能够相互交换)」或「ssgoalgoal 不同的字符数量为 00,但同时 ss 中有出现数量超过 22 的字符(能够相互交换)」时,两者必然为亲密字符。


代码:


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


  • 时间复杂度:令 nn 为两字符串之间的最大长度,CC 为字符集大小,CC 固定为 2626,复杂度为 O(n + C)O(n+C)
  • 空间复杂度:O(C)O(C)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.859 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
算法 计算机视觉 开发者
|
前端开发 编译器 开发者
CSS预处理器的优缺点
CSS预处理器的优缺点
131 0
[笔记]音视频学习之SDL篇《五》裁剪图片成子图片(裁剪精灵表)
[笔记]音视频学习之SDL篇《五》裁剪图片成子图片(裁剪精灵表)
145 0
|
12月前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
139 1
|
存储 关系型数据库 MySQL
PolarDB-X 存储引擎核心技术 | 索引回表优化
数据库系统为了高效地存储、检索和维护数据,采用了多种不同的数据组织结构。不同的组织结构有其特定的用途和优化点,比如提高查询速度、优化写入性能、减少存储空间等,目前 PolarDB-X 采用了 B-Tree 的索引组织结构。
|
数据可视化 数据挖掘
R语言k-means聚类、层次聚类、主成分(PCA)降维及可视化分析鸢尾花iris数据集
R语言k-means聚类、层次聚类、主成分(PCA)降维及可视化分析鸢尾花iris数据集
|
JSON 前端开发 Java
JAVA后端向前端传递Long类型数据,导致数据不一致
JAVA后端向前端传递Long类型数据,导致数据不一致
1744 0
|
数据可视化 Java Maven
爆赞!GitHub上首本IntelliJ IDEA操作手册,标星果然百万名不虚传
还记得刚开始工作的时候使用的是Eclipse,后面是当时公司第一批尝鲜IDEA的人。刚开始用起来其实蛮麻烦的,因为最开始还是带着Eclipse的思维。 比如在Eclipse中一个workspace中可以有多个project,但是在IDEA中就没有workspace的概念了,取而代之的是project,一个project中可以有多个module。 已经不止N次的被读者问到有没有IDEA的教程,其实我觉得这就是一个工具,无非就是一个熟能生巧的过程。在N + 1次被问到的时候,我觉得有必要肝一份使用手册了!
108 1
|
存储 监控 算法
操作系统引论
操作系统引论
167 0
全网首发:编译jna:dispatch.h:30:34: fatal error: com_sun_jna_Function.h: 没有那个文件或目录
全网首发:编译jna:dispatch.h:30:34: fatal error: com_sun_jna_Function.h: 没有那个文件或目录
133 0