【leetcode】Isomorphic Strings

题目简述:

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.

解题思路:

首先,相同的地方必须相同这个条件可以得出一个O(n^2)的算法

class Solution:
# @param {string} s
# @param {string} t
# @return {boolean}
def isIsomorphic(self, s, t):
ls = len(s)
lt = len(t)
if ls != lt:
return False
for i in range(ls):
for j in range(ls):
if s[i] == s[j]:
if t[i] != t[j]:
return False
return True

但是很不幸超时了,于是我们用hash的方法得到另一个更快的算法:

class Solution:
# @param {string} s
# @param {string} t
# @return {boolean}
def isIsomorphic(self, s, t):
ls = len(s)
lt = len(t)
if ls != lt:
return False
dic = {}
dic2 = {}
for i in range(ls):
if s[i] not in dic.keys():
dic[s[i]] = t[i]
else:
if dic[s[i]] != t[i]:
return False
if t[i] not in dic2.keys():
dic2[t[i]] = s[i]
else:
if dic2[t[i]] != s[i]:
return False
return True
上一篇:GIS 基础知识简介


下一篇:时间字符串格式化 js