当前位置: 首页 > news >正文

LeetCode150道面试经典题--同构字符串(简单)

1.题目

  1. 给定两个字符串 s 和 t ,判断它们是否是同构的。
  2. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。
  3. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。

2.示例/提示


3.思路

哈希表:

        首先两个字符串如果长度不相等,那么一定是不会一一对应的。然后一个键映射一个值,很明显就能联想到使用哈希表(HashMap),一次遍历一个字符串,当s串中遍历时候遇到map中不存在的键并且当前的值并不对应前面的键的时候,那么就通过put方法让两者一一对应。而如果遇到存在的键时候,就需要将存在的键对应的值与当前值比较,如果不一致则返回false。如果一直没有提前返回false,则最后输出true

如果不熟悉哈希表或者忘了相关内容可以在此复习Java类集框架(二)_Alphamilk的博客-CSDN博客

4.代码

LeetCode代码:

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

时间复杂度O(n)空间复杂度O(1)

在仔细想了一下之后,没找到内存可以优化的地方,再看了一下原来大伙都是用同解

详细案例代码:

package LeetCode13;import java.util.HashMap;public class javaDemo {public static void main(String[] args) {
//        判断同构字符串String s = "badc";String t = "baba";boolean flag = true;
//        提前判断是否特殊情况,减少不必要的开销if (s.length()!=t.length()){flag = false;}
//        创建哈希表HashMap<Character,Character> map = new HashMap<>();
//        s串遍历for (int i=0;i<s.length();i++){
//            当s串当前遍历的元素并不是map中的键时候if (!map.containsKey(s.charAt(i))){
//                在不存在map的前提下,如果当前值已经被前面的键用了那么直接输出失败if (map.containsValue(t.charAt(i))){flag = false;break;}
//                否则就将键值一一对应map.put(s.charAt(i),t.charAt(i));}else {
//                当当前遍历键存在时候,则通过get得到键对应的值再与当前值比较if (map.get(s.charAt(i)) != t.charAt(i)){flag = false;break;}}}
//        最后输出结果System.out.println(flag);}
}

http://www.lryc.cn/news/121088.html

相关文章:

  • Redis - 数据类型映射底层结构
  • MySQL数据库表的增删查改 - 进阶
  • 8086汇编语言工作环境 百度网盘下载
  • ES6 解构
  • React三个状态时触发的相应钩子
  • 阿里云服务器部署Drupal网站教程基于CentOS系统
  • 【广州华锐视点】VR燃气轮机故障判断模拟演练系统
  • 第01天 什么是CSRF ?
  • uniapp 自定义手机顶部状态栏不生效问题
  • C++语法中bitset位图介绍及模拟实现
  • Debezium系列之:深入理解消息过滤,实现过滤数据库删除事件,只采集数据库新增和更新事件
  • Substack 如何在去中心化内容创作领域掀起波澜
  • 【MFC】07.MFC六大机制:消息映射-笔记
  • python操作数据库
  • 【C语言】小游戏-三字棋
  • 多线程与并发编程面试题总结
  • 在多页面应用和单页面应用中(例如vue)怎么提高seo搜索引擎优化
  • Dubbo 2.7.0 CompletableFuture 异步
  • pytest-xdist分布式测试原理浅析
  • 研发工程师玩转Kubernetes——PVC通过storageClassName进行延迟绑定
  • 6.利用matlab完成 符号矩阵的秩和 符号方阵的逆矩阵和行列式 (matlab程序)
  • python获取类名__qualname__,解决django接口ObjectDoesNotExist异常寻找model的问题
  • 电流的测量(分流电流表)
  • Leetcode每日一题:23. 合并 K 个升序链表(2023.8.12 C++)
  • 越南的区块链和NFT市场调研
  • MySQL常用语句
  • Mongodb:业务应用(1)
  • 【vue】vue中按钮权限控制:
  • 【博客695】k8s subPathExpr作用
  • 微信小程序中键盘弹起输入框自动跳到键盘上方处理