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.
题目标签:Hash Table
题目给了我们两个string, 让我们判断它们是不是isomorphic。
只有当两个string的 char 是 1对1 map的时候,才是isomorphic,那么来看一下两个情况,它们不是 1对1 map:
1. bar foo
map:
b -> f
a -> o
r -> o
这种情况就是 左边两个chars map 到了 同一个 右边的 char;
2. bb fa
map:
b -> f
b -> a
这种情况就是 右边两个chars map 到了 同一个 左边的char;
所以只要遇到这两种情况,返回false,剩下的就是true。
Java Solution:
Runtime beats 57.23%
完成日期:05/26/2017
关键词:HashMap
关键点:利用HashMap来记录1对1map
class Solution
{
public boolean isIsomorphic(String s, String t)
{
HashMap<Character, Character> map = new HashMap<>(); for(int i=0; i<s.length(); i++)
{
char sChar = s.charAt(i);
char tChar = t.charAt(i); if(map.containsKey(sChar))
{
if(!map.get(sChar).equals(tChar)) // case 1: two different right chars map to one left char
return false;
}
else
{
if(map.containsValue(tChar)) // case 2: two different left chars map to one right char
return false; map.put(sChar, tChar);
} } return true;
}
}
参考资料:N/A
LeetCode 题目列表 - LeetCode Questions List