【哈希】Leetcode 205. 同构字符串【简单】

同构字符串

  • 给定两个字符串 s 和 t ,判断它们是否是同构的。

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

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

示例 1:

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

解题思路

  • 可以使用两个哈希表来解决这个问题。遍历字符串 s 和 t, 分别维护两个哈希表来记录字符之间的映射关系。
  • 如果遇到一个新的字符,则将其映射到另一个新的字符上,并将映射关系存储在哈希表中;
  • 如果遇到已存在的字符,则检查其映射关系是否与另一个字符串相符,如果不符则返回 false。
  • 如果遍历完成后未出现问题,则返回 true。

Java实现

public class IsomorphicStrings {public boolean isIsomorphic(String s, String t) {if (s.length() != t.length()) {return false;}Map<Character, Character> sMap = new HashMap<>();Map<Character, Character> tMap = new HashMap<>();for (int i = 0; i < s.length(); i++) {char sCh = s.charAt(i);char tCh = t.charAt(i);//s映射t要一一对应if (!sMap.containsKey(sCh)) {sMap.put(sCh, tCh);} else if (sMap.get(sCh) != tCh) {return false;}//t映射s也要一一对应if (!tMap.containsKey(tCh)) {tMap.put(tCh, sCh);} else if (tMap.get(tCh) != sCh) {return false;}}return true;}public static void main(String[] args) {IsomorphicStrings isomorphicStrings = new IsomorphicStrings();String s1 = "badc", t1 = "baba";System.out.println("Test Case 1:");System.out.println("s: \"egg\", t: \"add\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s1, t1)); // Expected: trueString s2 = "foo", t2 = "bar";System.out.println("\nTest Case 2:");System.out.println("s: \"foo\", t: \"bar\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s2, t2)); // Expected: falseString s3 = "paper", t3 = "title";System.out.println("\nTest Case 3:");System.out.println("s: \"paper\", t: \"title\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s3, t3)); // Expected: true}
}

时间空间复杂度

  • 时间复杂度: 遍历字符串 s 和 t,时间复杂度为 O(n),其中 n 是字符串的长度。

  • 空间复杂度: 使用了两个哈希表来存储映射关系,空间复杂度为O(n),其中 n 是字符串的长度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1424874.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

redis7基础篇2 redis的3种模式(主从,哨兵,集群)模式

一 主从复制模式 1.1 主从模式 主从模式&#xff1a; 主机可以读&#xff0c;写&#xff0c;重机只能写操作。 主机shutdown后&#xff0c;从机上位还是原地待命&#xff1a;从机不动&#xff0c;原地待命&#xff0c;数据正常使用&#xff0c;等待主机重启归来。 主机shu…

【Docker学习】查询容器镜像的docker search

这个命令是使用Docker的必备技能。我们使用的各种官方镜像&#xff0c;一般都能通过这个命令找到。 命令&#xff1a; docker search 描述&#xff1a; 在Docker Hub上查找镜像。Docker Hub是为开发者和开源贡献者设计的容器镜像注册中心&#xff0c;它允许用户查找、使用和…

《天空之城》观后感

曾经很长一段时间都着迷于《天空之城》这段旋律&#xff0c;一遍一遍不厌其烦地听&#xff0c;静谧而温馨、豪迈却苍凉&#xff0c;各种复杂的感受随着起伏的音符流淌进心里。多年之后才知道这首曲子出自宫崎骏的同名动画电影。说来也有意思&#xff0c;似乎大多数人是通过电影…

TypeScript中的泛型(Generics)

TypeScript中的泛型&#xff08;Generics&#xff09; 在前面的几篇文章中&#xff0c;我们了解了TypeScript的类、接口和基本的数据类型系统。本文将重点介绍TypeScript中的泛型&#xff0c;这是一种强大的工具&#xff0c;它允许我们创建可重用的组件&#xff0c;同时保持类…

AI网络爬虫:用kimi提取网页中的表格内容

一个网页中有一个很长的表格&#xff0c;要提取其全部内容&#xff0c;还有表格中的所有URL网址。 在kimi中输入提示词&#xff1a; 你是一个Python编程专家&#xff0c;要完成一个编写爬取网页表格内容的Python脚步的任务&#xff0c;具体步骤如下&#xff1a; 在F盘新建一个…

三.使用HashiCorp Vault工具管理数据库

三.ubuntu安装使用HashiCorp Vault工具管理数据库 HashiCorp Vault 是一个基于身份的秘密和加密管理系统。机密是您想要严格控制访问的任何内容,例如 API 加密密钥、密码和证书。Vault 提供由身份验证和授权方法门控的加密服务。使用 Vault 的 UI、CLI 或 HTTP API,可以安全…

SAP_ABAP-思考篇

作为一个SAP十年左右的从业者&#xff0c;其实我很清楚&#xff0c;我自身的能力&#xff0c;确实是很多东西都会一点&#xff0c;但是没有一样是精通的。坦白来说&#xff0c;我的个人简介里&#xff0c;虽然也不算夸大&#xff0c;但我估计有些新手小白看着可能会觉得还挺厉害…

VS2022如何添加现有项

以 想在队列里&#xff0c;使用堆栈的.c&#xff0c;.h文件 为例 目录 1.复制堆栈的.c&#xff0c;.h文件 ​编辑 2.打开队列所在项目的文件夹 3.粘贴堆栈的.c&#xff0c;.h文件 4.在头文件和源文件添加相应的堆栈的.c&#xff0c;.h文件 1.复制堆栈的.c&#xff0c;.h文件…

【智能算法】清道夫优化算法(CFO)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献5.代码获取 1.背景 2024年&#xff0c;W Zhang受到清道夫自然行为启发&#xff0c;提出了清道夫优化算法&#xff08;Cleaner Fish Optimization Algorithm, CFO&#xff09;。 2.算法原理 2.1算法思想 CF…

git常用命令及其ignore文件

1.git本地操作命令 # 查看git的版本 git --version # 生成空的本地仓库 git init # 将文件添加到暂存区 git add 文件 # 将暂存区里的文件提交到本地仓库 git commit -m "描述"2.git远程仓库命令 # 添加远程仓库 git remote add origin http://192.168.1.130:9000/…

开源的图形化Windows软件安装升级方案:WingetUI

WingetUI&#xff1a;简化数字生活&#xff0c;WingetUI让软件管理轻松便捷- 精选真开源&#xff0c;释放新价值。 概览 WingetUI是在GitHub上开发的一个实用工具&#xff0c;专为Windows用户设计&#xff0c;旨在为常见的命令行包管理工具&#xff08;如Winget、Scoop、Pip、…

AI图书推荐:ChatGPT 和Power BI驱动未来金融投资变革

《ChatGPT 和Power BI驱动未来金融变革》&#xff08;The Future of Finance with ChatGPT and Power BI&#xff09;由James Bryant和Aloke Mukherjee撰写&#xff0c;探讨了ChatGPT和Power BI在金融领域的应用。 主要特点&#xff1a; - 使用ChatGPT自动化Power BI&#xff…

基于振幅跟踪技术监测Inylchek冰川(吉尔吉斯斯坦)的冰流表面速度

冰川是重要的淡水资源&#xff0c;Inylchek冰川是世界上最长的冰川之一&#xff0c;60km长&#xff0c;有南北两个分支&#xff0c;海拔3000-4000米&#xff0c;最小坡度2。 2007年8月24日的Landsat5数据上的Inylchek冰川 为了监测冰川的运动&#xff0c;本研究获取了高重访周…

代码随想录算法训练营第五十四天

第二题我看了很久还是没太明白&#xff0c;我发现理解动规有一点点吃力了啊&#xff0c;努努力。 392.判断子序列 总感觉在不等于的时候&#xff0c;应该是dp[i][j] dp[i-1][j-2]; 这里其实按他那个图会更好理解一点。 class Solution { public:bool isSubsequence(string s, …

C++ I/O流(一)——输出流

一、IO流概念 IO流可分为输入流和输出流,用于从设备(如键盘、文件、网络等)读取数据或向设备写入数据。C++标准库提供了丰富的IO流类,包括iostream、fstream、stringstream等,分别用于处理控制台输入输出、文件输入输出和字符串流操作。 读操作:输入流中读取数据到程序中…

代码随想录--链表--反转链表

题目 题意&#xff1a;反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 思路 如果再定义一个新的链表&#xff0c;实现链表元素的反转&#xff0c;其实这是对内存空间的浪费。 其实只需要改变链表的next指针的…

蓝桥杯 EDA 组 历届国赛真题解析

一、2021年国赛真题 1.1 CN3767 太阳能充电电路 CN3767 是具有太阳能电池最大功率点跟踪功能的 4A&#xff0c;12V 铅酸电池充电管理集成电路。 最大功率点应指的是电池板的输出电压&#xff0c;跟踪电压其做保护。当然 CN3767 也可以直接使用直流充电&#xff0c;具体可以阅读…

API数据对接:本地缓存与日志记录的重要性

关键词&#xff1a;数据治理项目、API接口、数据中心、第三方系统、数据异常、本地缓存、日志记录、数据整合、多源异构数据、数据处理效率 阅读建议&#xff1a; 对于数据治理、API接口和系统集成领域的专业人士&#xff0c;本文深入剖析了本地缓存和日志记录在确保系统稳定性…

文档分类FastText模型 (pytorch实现)

文档分类FastText FastText简介层次softmaxN-gram特征FastText代码&#xff08;文档分类&#xff09; FastText简介 FastText与之前介绍过的CBOW架构相似&#xff0c;我们先来会议一下CBOW架构&#xff0c;如下图&#xff1a; CBOW的任务是通过上下文去预测中间的词&#xff0…

Python——IO编程

IO在计算机中指Input/Output&#xff0c;也就是输入和输出。由于程序和运行时数据是在内存中驻留&#xff0c;由CPU这个超快的计算核心来执行&#xff0c;涉及到数据交换的地方&#xff0c;通常是磁盘、网络等&#xff0c;就需要IO接口。 比如你打开浏览器&#xff0c;访问新浪…