Topic:
Given two strings s and *t*, determine whether they are isomorphic.
If the characters in S can be replaced with *t*, then the two strings are isomorphic.
All occurrences of characters must be replaced with another character, while preserving the order of the characters. Two characters cannot be mapped to the same character, but a character can map itself.
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.
Example 1:
Enter: s ="egg", t = "add"Output:true
Copy the codeExample 2:
Enter: s ="foo", t = "bar"Output:false
Copy the codeExample 3:
Enter: s ="paper", t = "title"Output:true
Copy the codeNote: You can assume that s and *t* have the same length.
Note: You may assume both *s* and *t* have the same length.
Answer:
In example 3, enter: s = “paper”, t = “title”, where the letter mapping results: P <==> t, A <==> I, E <==> L, r <==> E can be replaced one by one to obtain the corresponding word, which is an isomorphic string.
There are no more than two cases of non-isomorphic strings (assuming equal lengths) :
s = 'aa' , t = 'ab', in the establishment of a letter mapa <==> aAfter, s the mapping of the second letter avalue = aNot equal to the second letter b in ts = 'ab' , t = 'aa', in the establishment of a letter mapa <==> bAfter t, the mapping of the second letter akey = aNot equal to the second letter b in s
So this can either be verified by two hash maps, or it can be verified by a map plus whether it exists in its values.
Since you’re building mapping characters, the first thing that comes to mind is hash maps (maps, dict).
The title of isomorphism detection of English word string, the length of the entire ASCll code is only 256, so this problem can also use char[256] to establish a mapping relationship with the index value corresponding to a character, and its stored value corresponding to a character.
A more subtle solution is to compare each character to the first occurrence of the index in the string to determine whether it is isomorphic. Such as:
Enter: s ='aa' , t = 'ab'First character in the first traversal: s index is 0, the first time a t the first character in the index is 0, the first time a index are equal, continue to traverse Second traversal, the second character in the s a index of 0 for the first time, the second character in the t b index is 1, the first time index are not equal, to returnfalse
Copy the codeCode:
Double hash mapping:
Java:
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s_map = new HashMap<>();
Map<Character, Character> t_map = new HashMap<>();
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray(); // Convert to a cahr array
for (int i = 0; i < s_chars.length; i++) {
// Two cases that are not true
if(s_map.containsKey(s_chars[i]) && s_map.get(s_chars[i]) ! = t_chars[i])return false;
if(t_map.containsKey(t_chars[i]) && t_map.get(t_chars[i]) ! = s_chars[i])return false;
s_map.put(s_chars[i], t_chars[i]);
t_map.put(t_chars[i], s_chars[i]);
}
return true; }}Copy the codePython:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_map, t_map = {}, {} # double dictionary
for c1, c2 in zip(s, t):
# Two false cases
if c1 in s_map ands_map[c1] ! = c2:return False
if c2 in t_map andt_map[c2] ! = c1:return False
s_map[c1] = c2
t_map[c2] = c1
return True
Copy the codeSingle hash mapping:
Java:
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap<>();// a hash map
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
for (int i = 0; i < s_chars.length; i++) {
if(map.containsKey(s_chars[i]) && map.get(s_chars[i]) ! = t_chars[i])return false;
// Check whether the character in t exists in values in the mapping
if(! map.containsKey(s_chars[i]) && map.containsValue(t_chars[i]))return false;
map.put(s_chars[i], t_chars[i]);
}
return true; }}Copy the codePython:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
hash_map = {}
for c1, c2 in zip(s, t):
if c1 in hash_map andhash_map[c1] ! = c2:return False
Check whether the character in t exists in values in the mapping
if c1 not in hash_map and c2 in hash_map.values():
return False
hash_map[c1] = c2
return True
Copy the codeIndex comparison for the first occurrence of a character:
Java:
class Solution {
public boolean isIsomorphic(String s, String t) {
char[] s_chars = s.toCharArray();
char[] t_chars = t.toCharArray();
for (int i = 0; i < s.length(); i++) {
// Determine if the index value of the first occurrence of this character is equal
if(s.indexOf(s_chars[i]) ! = t.indexOf(t_chars[i])) {return false; }}return true; }}Copy the codePython:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
for c1, c2 in zip(s, t):
# determine if the index value of the first occurrence of the character is equal
ifs.find(c1) ! = t.find(c2):return False
return True
Copy the code256 bit character mapping
Java
class Solution {
public boolean isIsomorphic(String s, String t) {
char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
char[] s_map = new char[256], t_map = new char[256]; // Index is mapped to stored values
for (int i = 0; i < s_chars.length; i++) {
char sc = s_chars[i], tc = t_chars[i];
if (s_map[sc] == 0 && t_map[tc] == 0) {
s_map[sc] = tc;
t_map[tc] = sc;
} else if(s_map[sc] ! = tc || t_map[tc] ! = sc) {// Whether the mapping between index and element value meets the condition
return false; }}return true; }}Copy the codeCharacters are not the basic data in Python
Welcome to follow Wechat. The letter. The male. All the. Number: Love to write bugs