首页 > 其他分享 >同构字符串

同构字符串

时间:2024-05-31 10:44:24浏览次数:20  
标签:字符 同构 HashMap 映射 哈希 字符串

题目:

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

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

示例 1:
输入:s = "egg", t = "add"
输出:true
示例 2:
输入:s = "foo", t = "bar"
输出:false
示例 3:
输入:s = "paper", t = "title"
输出:true

提示:
1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

首先我们来分析这个题目的要求是什么,当然这一块看起来像是在做语文题。不过在我们的实际生活和工作中,善于与人沟通也是一个很重要的技能嘛。

egg add, 这两个字符串如果把左边的e改为a,g改为d就可以完美的将add改为egg。这就说明add和egg是同构字符串;左边的每一个字符都只能有一个替代者。

那么我们很容易可以想到哈希表可以让我们对字符串中的每一个字符都有一个固定的映射。

现在我们知道了,我们需要2个哈希表。

 Map<Character, Character> s2t = new HashMap<Character,Character>();
 Map<Character, Character> t2s = new HashMap<Character,Character>();


在两个哈希表中,哈希值为另一个字符串的字符,存储的元素为本字符串的字符。也就是说,S字符串的字符存储在s2t这个哈希表中,s的字符存进的位置的编号为t的对应位置的字符。这样我们只需要判断,每一次存储进对应的字符时,之前有没有出现过不一样的对应值

完整代码

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character,Character>();
        Map<Character, Character> t2s = new HashMap<Character,Character>();

        int len = s.length();

        for(int i=0;i<len;++i){
            char x = s.charAt(i), y = t.charAt(i); //获取s和t在 i 位置的字符,并存储进x和y
            if((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)){   //双向验证,只要有一边的字符对不上另一边的字符便返回false
                return false;
            }

            s2t.put(x,y);
            t2s.put(y,x);
        }

        return true;
    }
}

标签:字符,同构,HashMap,映射,哈希,字符串
From: https://www.cnblogs.com/Radioactive/p/18221209

相关文章

  • SAP ABAP 字符串去除重复字符的两种方法
    ABAP里如何去除字符串内的重复字符,在这提供两种方法。第一种是直接对字符串多次循环进行排除,但考虑到性能问题要尽量减少循环次数。第二种是把字符串里字符转成内表一列,去重后拼回一个字符串。方法一示例代码:点击查看代码DATAmarkTYPEc.......
  • 【算法】范围尝试模型、已有字符串添加最少字符使其成为回文字符串
    1.概述给定一个字符串str,如果可以在str的任意位置添加宇符,请返回在添加字符最少的情況下,让str整体都是回文字符串的一种结果。【举例】str="ABA"str本身就是回文串,不需要添加字符,所以返回"ABA"str="AB"可以在’A'之前添加’B'使str整体都是回文串,故可以返回"BAB"......
  • 简化路径为符合unix风格的字符串
    题目给你一个字符串path,表示指向某一文件或目录的Unix风格绝对路径(以'/'开头),请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点(..)表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的......
  • 如何了解转义字符和字符串的细节运用?
    1.什么是转义字符呢?转义字符是一组特殊的字符转义字符顾名思义:转变原来的意思的字符例如:‘n’原本就是简单字符n 如果加上/那么/n转变换行的意思2.那么转义字符有那些呢?\?:在书写连续多个问号时使用,防止他们被解析成三字母词,在新编译器上无法验证三字母词??( --[?......
  • 代码随想录算法训练营Day55 | 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总
    本文目录583.两个字符串的删除操作做题看文章72.编辑距离做题看文章编辑距离总结篇以往忽略的知识点小结个人体会583.两个字符串的删除操作代码随想录:583.两个字符串的删除操作Leetcode:583.两个字符串的删除操作做题找出最长公共子序列,然后用两个字符串的......
  • Jackson序列化为字符串时对指定字段脱敏
    枚举脱敏字段类型及规则importjava.util.function.Function;publicenumTextMaskStrategy{ID_NO("身份证",18,text->"*".repeat(text.length()-4)+text.substring(text.length()-4)),PHONE("手机号",11,text->text.substr......
  • 未验证:字符串解析为字典的九种方法/
    我是说直接把字典里的内容变成字符串然后解析这个字符串为字典然后才是代码中的计算,我是让你修改代码将输出字符串解析为字典的九种方法:方法一:使用正则表达式importreparsed_item_prices={}current_item=Noneforlineinoutput_string.split('\n'):if......
  • python-旋转字符串
    问题描述:给定一个字符串(以字符串数组的形式)和一个偏移量,根据偏移量从左到右地旋转字符数组。问题示例:输入str=”abcdefg”,offset=3,输出“efgabcd”。输入str=”abcdefg”,offset=0,输出“abcdefg”。(返回旋转后的字符串) 完整代码如下:a=list(input().split())n=int(inpu......
  • C#去掉字符串首尾字符
    以下是多种不同的实现方法来去除C#字符串的首尾字符:1、使用Substring方法:stringinput="HelloWorld!";stringoutput=input.Substring(1,input.Length-2);2、使用Remove方法:stringinput="HelloWorld!";stringoutput=input.Remove(0,1).Remove(input.Leng......
  • LeetCode 第8题:字符串转换整数 (atoi)
    本文我们来看看LeetCode第8题.字符串转换整数(atoi)的解析过程。文章目录一、引言题目描述示例二、解题思路1.丢弃无用的前导空格2.处理正负号3.读入数字4.处理整数溢出5.组合起来思路流程图三、Java代码实现代码解析1.移除前导空格2.处理正负号3.转换数......