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

news/2024/4/16 21:05:37

❓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软…

(05)基础强化:字符串拘留池,格式化,StringBuilder,垃圾回收,弱引用

一、复习 1.什么是接口&#xff1f;说说你对接口的理解。 &#xff08;提示&#xff1a;概念、语法、应用场景&#xff0c;与抽象类的区别。说出最特别的&#xff09; 接口是一种规范、标准&#xff0c;一种抽象的概念&#xff0c;所以本身无法实现&#…

关于对于springcloud中的注册中心和consume消费者和provier服务者之间的关系理解

关于对于springcloud中的注册中心和consume消费者和provier服务者之间的关系理解 pringCloud provider&#xff08;服务提供方&#xff09; consumer&#xff08;服务调用方&#xff09; server&#xff08;注册中心&#xff09; 运行原理 Provider 第一步 provider注册到se…

Ansible的脚本-playbook 剧本

目录 1.剧本&#xff08;playbook&#xff09; 1.playbook介绍 2. playbooks 的组成 3.案例&#xff1a;编写httpd的playbook 4.定义、引用变量 5.指定远程主机sudo切换用户 6.when条件判断 7.迭代 2.playbook的模块 1.Templates 模块 2.tags 模块 3.Roles 模块 1.…

SpringBoot定义优雅全局统一Restful API 响应框架二

这里解决之前留下来的问题&#xff0c;当程序没有正常返回时候 就是程序由于运行时异常导致的结果&#xff0c;有些异常我们可&#xff0c;能无法提前预知&#xff0c;不能正常走到我们return的R对象返回。这个时候该如何处理 在SpringBoot中&#xff0c;可以使用ControllerA…

ctfshow之_萌新web1至web7

一、访问在线靶场ctfshow ctf.showhttps://ctf.show/challenges如下图所示&#xff0c;进入_萌新赛的web1问题&#xff1a; 如上图所示&#xff0c;页面代码提示id1000时&#xff0c;可以查询到flag&#xff0c;进行如下尝试&#xff1a; 如下图所示&#xff0c;传入参数id1时…

DAY 47 Ngnix优化与防盗链

Ngnix优化主要有两种&#xff0c;一种是配置上的优化&#xff0c;一种是内核上的优化 隐藏响应头中的版本号 方法一&#xff1a;curl命令 网页查看 隐藏版本信息 修改nginx的运行用户和组 方法一&#xff1a;在编译安装时&#xff0c;指定运行用户和组 [root nginx-1.12.2]#…

JoJo‘s Incredible Adventures

题目&#xff1a; 题意解析&#xff1a; 这个题目是要求找出输入的字符串&#xff0c;&#xff0c;字符串的循环移位s由k右边是字符串Sn−k1...Sn&#xff0c;S1&#xff0c;S2...Sn−k。直到所有的字符&#xff0c;都循坏出现在字符串的开头&#xff0c;然后输入1形成的长方形…

「SQL面试题库」 No_55 销售分析 I

&#x1f345; 1、专栏介绍 「SQL面试题库」是由 不是西红柿 发起&#xff0c;全员免费参与的SQL学习活动。我每天发布1道SQL面试真题&#xff0c;从简单到困难&#xff0c;涵盖所有SQL知识点&#xff0c;我敢保证只要做完这100道题&#xff0c;不仅能轻松搞定面试&#xff0…

【云原生Kubernetes】01-Kubernetes简介

【云原生Kubernetes】01-Kubernetes简介 文章目录 【云原生Kubernetes】01-Kubernetes简介前言kubernets概述为什么要使用Kubernetes?Kubernetes能做什么&#xff1f;Kubenets架构架构图架构组件说明Master节点Node节点Etcd节点 组件间的工作流程 Kubernetes的核心技术Pod副本…

Java Web应用开发 ——第三章:JSP内置对象测试

一.单项选择题&#xff08;共15题,60.0分&#xff09; 1 使用response对象进行重定向时&#xff0c;使用的方法是&#xff08; A、 setAttribute B、 sendRedirect C、 setContentType D、 getAttribute 正确答案&#xff1a; B 2 session对象中用于设定指定名字的属性值…

ElasticSearch(二)简介

1. 简介 Elasticsearch 是一个分布式、高扩展、高实时的搜索与数据分析引擎。 它能很方便的使大量数据具有搜索、分析和探索的能力。充分利用Elasticsearch的水平伸缩性&#xff0c;能使数据在生产环境变得更有价值。 Elasticsearch 的实现原理主要分为以下几个步骤&#xf…

@RestControllerAdvice注解

目录 1. RestControllerAdvice注解 详解&#xff1a; 1.1 概述 1.2 用途&#xff1a; 1.3 基本使用&#xff1a; 1.4 属性&#xff1a; annotations: basePackages: basePackageClasses: assignableTypes: 1.5 与ExceptionHandler的结合&#xff1a; 1.6 总结 2. R…
最新文章