本文共 1397 字,大约阅读时间需要 4 分钟。
题目描述
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中同一个字母替换,paper的p被title的t替换了,那么下一次出现p的地方一定对应t
从1到length遍历,建立一个hash表用于标识出现过的字母,这里需要注意,组成字符串的字符可以是ascii码中的任意,ascii码由0~255,所以建立两个int[256]用来记录 最终目的就是验证这次a对应b下次出现a的时候对应的还得是b
int[] apls = new int[256];int[] aplt = new int[256]; for(int i = 0;i < s.length();i++){ if(apls[s.charAt(i)]!=aplt[t.charAt(i)])return false; apls[s.charAt(i)] = i+1; aplt[t.charAt(i)] = i+1; }return true;也可以将s字符和t的字符建立映射,但是光每对映射相同还不行,t中字符智能对应一种映射,他们是一对一映射
int[] apl = new int[256]; Setset = new HashSet(); for(int i = 0;i < s.length();i++){ if(apl[s.charAt(i)] == 0){ if(set.add((int)t.charAt(i))){ apl[s.charAt(i)] = (int)t.charAt(i); }else return false; } else if(apl[s.charAt(i)]!=(int)t.charAt(i))return false; } return true;
转载地址:http://ohdvi.baihongyu.com/