【LeetCode】205. Isomorphic Strings 解题报告(Java & Python)
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/isomorphic-strings/#/description
题目描述
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note:
- You may assume both s and t have the same length.
题目大意
看s到t的映射关系是不是一一映射的,s中不同的字符是不能映射到t的同一个字符的。
解题方法
字典保存位置
这个题可以看出来使用hashmap,但是,注意的一点是不要用位置++的方式,这样的话只统计了这个字符出现的次数,没有统计对应的位置,导致出错。比如aba
和baa
就会导致结果错误。因此,用到的是字符出现的位置+1的方式,保证能在hash位置处保存字符出现的位置。
public class Solution {
public boolean isIsomorphic(String s, String t) {
int[] m1 = new int[256];
int[] m2 = new int[256];
int len = s.length();
for(int i = 0; i < len; i++){
if(m1[s.charAt(i)] != m2[t.charAt(i)]){
return false;
}
m1[s.charAt(i)] = i + 1;
m2[t.charAt(i)] = i + 1;
}
return true;
}
}
字典保存映射
因为是一一映射关系,所以s到t和t到s的映射都要进行判断。最简单的方法就是使用两次判断,这样的话,我们可以分别看映射关系是不是一致的。
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
m = dict()
for i, c in enumerate(s):
if c in m:
if t[i] != m[c]:
return False
else:
m[c] = t[i]
m = dict()
for i, c in enumerate(t):
if c in m:
if s[i] != m[c]:
return False
else:
m[c] = s[i]
return True
既然想到了两次判断,那么我们应该也能想到,使用两个字典分别保存s到t的判断和t到s的判断。代码如下:
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
m = dict()
n = dict()
for i, c in enumerate(s):
if c in m and m[c] != t[i]:
return False
if t[i] in n and c != n[t[i]]:
return False
m[c] = t[i]
n[t[i]] = c
return True
日期
2017 年 5 月 15 日
2018 年 11 月 24 日 —— 周六快乐
最新文章
- C语言实现线程池
- POJ2406 Power Strings(KMP,后缀数组)
- Failed to connect to remote VM. Connection refused. Connection refused: connect.
- Nginx技巧:灵活的server_name,Nginx配置一个服务器多个站点 和 一个站点多个二级域名
- db2查看表空间
- 使用Powermock进行单元测试,以及常见问题的处理
- mysql数据库全局只读和会话只读问题解析
- android 实现跳动频谱 DEMO
- MySQL中数据表的增操作
- .Net Core Session验证码
- ASP.NET Core 2.1 : 十.升级现有Core2.0 项目到2.1
- docker(四) 使用Dockerfile构建镜像
- ASP.NET Core API 接收参数去掉烦人的 [FromBody]
- 修改AD中PCB各层的透明度
- 为什么开启子进程 一定要放在 if __name__ == &#39;__main__&#39; 下面
- Android手机流量分析工具介绍
- Code First 重复外键
- larabbs安装教程
- JAVA基础部分复习(三、泛型)
- ubuntu 搭建samba共享方案
热门文章
- 利用elliipse做相关图
- Flink 实践教程-进阶(2):复杂格式数据抽取
- tomcat拦截特殊字符报400,如 ";|"; ";{"; ";}"; ";,";等符号的解决方案
- C++构造函数和析构函数初步认识(2)
- Maven pom.xml报错解决
- Linux学习 - 数值运算
- Linux学习 - 输入输出重定向,管道符,通配符
- Output of C++ Program | Set 6
- Mybatis-运行原理
- oracle体系结构(图)