leetcode 205.同构字符串

news/2024/9/24 17:00:34/

思路:哈希表

这里用了两个哈希表。至于为什么,且看下面的思路:

首先我们的题目要求我们每一个字母映射一个对应的字母,并且每个字母映射的字母不能一样,也就是严格的一一对应。

关于映射,自然就会想到用哈希表来存储用。但是,我们要知道,哈希表的区分只是对于键的去重,而和元素的去重没有关系,所以我们开始在尝试直接用哈希表映射的时候,不同的字母可以映射一样的字母,这是和题目要求不匹配的。

所以我们需要考虑被映射的字母怎么处理。一般的处理方法就是做上标记,让程序知道这个字母已经被别的字母映射过了。所以我们可以再创建一个哈希表用来标记这个字母的状态。

注意:这里说的字母是不仅仅包括26个字母,大家不要误会。有人会想到用数组来标记,很显然不合理。用数组的话你需要开一个能包括所有ASCII码的数组大小,这对于空间开销有点大了,所以用哈希表会合算一点。

还有一点就是,我们被标记的字母,再次遍历到有字母要映射它时,是不会放到哈希表里面去的,除了判断映射的字母是否和t字符串中的字符一致以外,还需要判断这个字符是否存在这个哈希表映射中。

class Solution {public boolean isIsomorphic(String s, String t) {if(s.length()!=t.length())return false;Map<Character,Character>m=new HashMap<>();Map<Character,Integer>count=new HashMap<>();for(int i=0;i<s.length();i++){if(!count.containsKey(t.charAt(i))){count.put(t.charAt(i),1);m.put(s.charAt(i),t.charAt(i));}}for(int i=0;i<s.length();i++){if(!m.containsKey(s.charAt(i))||m.get(s.charAt(i))!=t.charAt(i)){return false;}}return true;}
}


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

相关文章

Kali Linux 2024.3

新版本&#xff0c;新特性 Kali Linux 2024.3 版本带来了一系列新功能和优化改进&#xff0c;包括但不限于&#xff1a; 新增对高通骁龙 SDM845 芯片的支持&#xff1a;Kali NetHunter Pro 设备现在支持更多设备&#xff0c;提升了 Kali 移动渗透测试平台的兼容性和实用性 系统…

【Verilog学习日常】—牛客网刷题—Verilog快速入门—VL22

根据状态转移图实现时序电路 描述 某同步时序电路的状态转换图如下&#xff0c;→上表示“C/Y”&#xff0c;圆圈内为现态&#xff0c;→指向次态。 请使用D触发器和必要的逻辑门实现此同步时序电路&#xff0c;用Verilog语言描述。 电路的接口如下图所示&#xff0c;C是单b…

Qt 状态机编程,双层状态机,实现暂停恢复

流程设计状态图 #ifndef WORKMACHINE_H #define WORKMACHINE_H#include <QObject> #include <QStateMachine> #include <QHistoryState> #include <QFinalState>#include "WorkThread.h"class WorkMachine : public QObject {Q_OBJECT publ…

汽车总线之---- CAN FD总线

CAN FD 最高可支持8M/s的通信速率&#xff0c;从传统CAN到CAN FD的转换是很容易实施和推广的。 CAN FD报文的帧&#xff1a;标准帧&#xff0c;扩展帧 CAN FD 标准帧结构 CAN FD 报文的标准帧与CAN 报文的标准帧的区别 CAN FD 报文的标准帧与CAN FD报文的扩展帧的区别&…

C++primer第十一章使用类(矢量随机游走实例)

操作符重载 操作符重载(operator overoading)是一种形式的 C多态。 第8章介绍了C是如何使用户能够定义多个名称相同但特征标(参数列表)不同的函数的。这被称为函数重载(function overloading)或函数多态(functional polymorphism)&#xff0c;旨在让您能够用同名的函数来完成…

简历信息提取系统源码分享

简历信息提取检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…

HP 电脑 - 管理电源选项 (Windows 10)

HP 电脑 - 管理电源选项 (Windows 10) 您可以选择 Windows 电源计划减少电脑使用的电量&#xff0c;最大限度提高性能&#xff0c;或者实现二者的完美平衡。此外&#xff0c;本文档还提供了多种关闭电脑的方法以及如何使用电源模式和解决电源问题等信息。 使用 Windows 电源计…

Java | Leetcode Java题解之第421题数组中的两个数的最大异或值

题目&#xff1a; 题解&#xff1a; class Solution {// 字典树的根节点Trie root new Trie();// 最高位的二进制位编号为 30static final int HIGH_BIT 30;public int findMaximumXOR(int[] nums) {int n nums.length;int x 0;for (int i 1; i < n; i) {// 将 nums[i…