( 字符串) 205. 同构字符串 ——【Leetcode每日一题】

news/2025/2/18 12:04:32/

❓205. 同构字符串

难度:简单

给定两个字符串 st ,判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。

示例 1:

输入:s = “egg”, t = “add”
输出:true

示例 2:

输入:s = “foo”, t = “bar”
输出:false

示例 3:

输入:s = “paper”, t = “title”
输出:true

提示:

  • 1 < = s . l e n g t h < = 5 ∗ 1 0 4 1 <= s.length <= 5 * 10^4 1<=s.length<=5104
  • t.length == s.length
  • st 由任意有效的 ASCII 字符组成

💡思路:

法一:定长数组

由于 st 由任意有效的 ASCII 字符组成,ASCII 对应的十进制为 0 ~ 255,所以可以定义两个长度为256的数组,就能包括所有字符:

  • 数组中记录一个字符上一次出现在字符串中的位置;
  • 如果两个字符串中的字符上一次出现的位置一样,那么就属于同构。

法二:哈希表

由于不同字符不能映射到同一个字符上,所以两个字符串的映射关系都必须一一对应,不能出现一对多的情况,这里设置两个哈希表,分别存储两个字符串中已建立映射关系的字符:

  • 同时遍历字符串 s 和字符串 t 的相同位置,建立映射关系;
  • 如果s 的字符已经在哈希表中,则判断t对应位置的字符是否等于哈希表中的映射,如果不等,则返回false,相等则继续遍历。
  • 如果字符串 st 的字符都不在哈希表中,则将st对应位置的映射关系存储到哈希表中;
  • 否则不是同构字符串,返回false
  • 最后返回true

🍁代码:(Java、C++)

法一:定长数组
Java

class Solution {public boolean isIsomorphic(String s, String t) {int[] preIndexOfS = new int[256];int[] preIndexOfT = new int[256];for(int i = 0; i < s.length(); i++){char sc = s.charAt(i), tc = t.charAt(i);if(preIndexOfS[sc] != preIndexOfT[tc]){return false;} preIndexOfS[sc] = i + 1;preIndexOfT[tc] = i + 1;}return true;}
}

C++

class Solution {
public:bool isIsomorphic(string s, string t) {vector<int> preIndexOfS(256);vector<int> preIndexOfT(256);for (int i = 0; i < s.size(); i++) {if (preIndexOfS[s[i]] != preIndexOfT[t[i]]) {return false;}preIndexOfS[s[i]] = i + 1;preIndexOfT[t[i]] = i + 1;}return true;}
};

法二:哈希表
Java

class Solution {public boolean isIsomorphic(String s, String t) {Map<Character, Character> mapping = new HashMap<>();Set<Character> setting = new HashSet<>();for(int i = 0; i < s.length(); i++){char sc = s.charAt(i), tc = t.charAt(i);if(mapping.containsKey(sc)){if(mapping.get(sc) != tc) return false;}else if(!setting.contains(tc)){mapping.put(sc, tc);setting.add(tc);}else{return false;}}return true;}
}

C++

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, char> mapping;unordered_set<char> setting;for(size_t i = 0; i < s.size(); i++){if(mapping.find(s[i]) != mapping.end()){if(mapping[s[i]] != t[i]) return false;}else if(setting.find(t[i]) == setting.end()){mapping.insert({s[i], t[i]});setting.insert(t[i]);}else{return false;}}return true;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串s的长度。
  • 空间复杂度 O ( S ) O(S) O(S),其中 S 为字符集大小。法一:我们使用了一个长度为 256 的数组,存储每个字符出现的次数。法二:哈希表存储字符的空间取决于字符串的字符集大小,最坏情况下每个字符均不相同。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/58022.html

相关文章

JavaScript中的模块化编程

JavaScript是一种强大的编程语言&#xff0c;它可以在浏览器中进行客户端脚本编写&#xff0c;并且在服务器端也有广泛的应用。随着JavaScript应用的增多&#xff0c;JavaScript代码的复杂度也不断增加。为了提高代码的可维护性和重用性&#xff0c;模块化编程变得越来越重要。…

JUnit 5 使用教程 及 JUnit 4/5的差异

1. JUnit 5产生的原因 JDK 8在java中带来了迷人的功能,最值得注意的是lambda表达式 为了适应 Java 8 风格的编码和新的功能特性,JUnit 提供了JUnit 5 2. JUnit 5 架构 与 JUnit 4 相比,JUnit 5 由来自三个不同子项目的几个不同模块组成:JUnit 5 = JUnit Platform + JUni…

Java NIO(Java Non-Blocking IO:非阻塞式IO)(2)

1.NIO非阻塞网络编程原理分析 1>.NIO非阻塞网络编程相关的(Selector、SelectionKey、ServerScoketChannel和SocketChannel)关系梳理图: 说明: ①.当客户端连接时,会通过服务器端ServerSocketChannel得到/生成对应的SocketChannel; ②.通过register(Selector sel,int ops)…

1 认识仿真工具Packet Tracer【实验】【计算机网络】

1 认识仿真工具Packet Tracer【实验】【计算机网络】 前言推荐1 认识仿真工具Packet Tracer1.1账号注册与Packet Tracer软件下载1.1.1 下载1.1.2 安装 1.2 Packet Tracer界面简介1.2.1 总述1.2.2 详细 1.3网络拓扑构建与设备模块添加1.3.1如何往工作区中添加设备1.3.2添加连线1…

【移动端网页布局】流式布局案例 ④ ( Banner 栏制作 | 固定定位 | 标准流 | 百分比宽度设置 )

文章目录 一、Banner 栏样式及核心要点1、实现效果2、核心要点分析 二、完整代码示例1、HTML 标签结构2、CSS 样式3、展示效果 一、Banner 栏样式及核心要点 1、实现效果 在上一篇博客中 , 实现了 搜索栏 , 在本篇博客开始实现 搜索栏 下方的 Banner 栏 ; 2、核心要点分析 Bann…

python:分层抽样(取出0和1中70%的数值)

分层抽样是一种从总体中抽取样本的方法&#xff0c;它将总体划分为若干个层次&#xff0c;然后在每一层中分别抽取样本。分层抽样可以保证每一层中的样本数量相对均衡&#xff0c;从而可以提高样本的代表性。在本文中&#xff0c;我将介绍分层抽样的原理、优点以及应用场景&…

大事件——100篇文章帮助小白顺利进入嵌入式领域

哈喽伙伴们&#xff0c;最近有很多刚入门的小白找到我&#xff0c;让我给一些学习方向。作为一个从嵌入式领域摸爬滚打到现在的“前辈”来说&#xff0c;对于每个小伙伴我都想倾囊相助&#xff0c;但是奈何本人的精力实在有限。所以综合考虑下&#xff0c;决定在这里开一个专栏…

真题详解(DNS)-软件设计(六十三)

真题详解&#xff08;有向图&#xff09;-软件设计&#xff08;六十二)https://blog.csdn.net/ke1ying/article/details/130443040 顺序存储&#xff1a;元素和存储空间相对位置来表示数据元素之间逻辑关系。 RFB&#xff1a;远程访问图形用户界面的简单协议。 在ISO/IEC9126软…