leetcode205 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.

Example 1:

Input: s = "egg", t = "add"
Output: true

209 Word Pattern

用到的语法：

python string split() method

txt = "welcome to the jungle"

x = txt.split()

['welcome', 'to', 'the', 'jungle']

solution 1: Two Hash Maps

pattern: ‘abba’

str: ‘dog cat fish dog’

pattern_dict = {a:0, b:1}

str_dict = {dog:0, cat:1, fish:2}

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        pattern_dict = {}
        str_dict = {}
        str_word = str.split()
        if len(pattern) != len(str_word):
            return False
        for i in range(len(pattern)):
            if pattern[i] not in pattern_dict:
                pattern_dict[pattern[i]] = i
            if str_word[i] not in str_dict:
                str_dict[str_word[i]] = i
        for i in range(len(pattern)):
            if pattern_dict[pattern[i]] != str_dict[str_word[i]]:
                return False
        return True

solution 2: Single Index Hash Map

pattern: ‘abba’

str: ‘dog cat fish dog’

map_index={ a:0 , dog:0 , b:1 , cat:1 , fish:2}

index of ‘b’ and index of ‘fish’ are NOT the same. Returns False.

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        map_index = {}
        words = str.split()
        
        if len(pattern) != len(words):
            return False
        
        for i in range(len(words)):
            c = pattern[i]
            w = words[i]

            char_key = 'char_{}'.format(c)
            char_word = 'word_{}'.format(w)
            
            if char_key not in map_index:
                map_index[char_key] = i
            
            if char_word not in map_index:
                map_index[char_word] = i 
            
            if map_index[char_key] != map_index[char_word]:
                return False
        
        return True

关于这里为什么要把char和string 区别开来：

如果不区别的话，

pattern=”abc”
str=”b c a”

Differentiating between character and string: In Python there is no separate char type. And for cases such as:

pattern: ‘abba’ str: ‘b a a b’

Using the same hash map will not work properly. A workaround is to prefix each character in pattern with “char_” and each word in str with “word_”.

solution 3:

def wordPattern(self, pattern, str):
    s = pattern
    t = str.split()
    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)

205 Isomorphic Strings

209 和 205 同思路，同方法

Solution 1:

s=”foo”

t=”bar”

check={ f:true, o:true}

dic={ f:b, o:a}

When i =index2

o and r return false, since o is already in check

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        dic={}
        check={}
        for i in range(len(s)):
            if s[i] in dic:
                if dic[s[i]]!=t[i]:
                    return False
            else:
                if t[i] in check:
                    return False
                dic[s[i]]=t[i]
                check[t[i]]=True
        return True

solution 3:

return len(set(zip(s, t))) == len(set(s)) == len(set(t))

python zip() 用法