【朱迪的LeetCode刷题笔记】205. Isomorphic Strings 同构字符串 #Easy #Python

Judie

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true


Constraints:
1 <= s.length <= 5 * 104
t.length == s.length
s and t consist of any valid ascii character.

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        
    }
};

Judy

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        d = {}
        for x, y in zip(s, t):
            if x not in d:
                if y not in d.values():
                    d[x] = y
                else:
                    return False
            elif d[x] != y:
                return False

        return True
        

Gray
c++ bad version?

#include <iostream>
#include <map>

#include <algorithm>

class Solution {
    
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> dict;
        
        for(int i = 0; i < s.size(); i++){
            vector<char> value;
            for(auto it = dict.cbegin(); it != dict.cend(); ++it){
                value.push_back(it->second);
            }
            if (dict.find(s[i])!=dict.end()){
                s[i] = dict[s[i]];
            }else {
                cout << "cycle" << endl;
                for(int j = 0; j < value.size();j++){
                    if(value[j] == t[i]){
                        return false;
                    }
                }
                dict[s[i]] = t[i];
                s[i] = t[i];
            }
        }
        if(s == t){
            return true;
        }else {
            return false;
        }

    }
};

c++ better version?

#include <iostream>
#include <map>

#include <algorithm>

class Solution {
    
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> dict;
        
        for(int i = 0; i < s.size(); i++){
            vector<char> value;

            if (dict.find(s[i])!=dict.end()){
                s[i] = dict[s[i]];
            }else {
                for(auto it = dict.cbegin(); it != dict.cend(); ++it){
                if(it->second == t[i]){
                   return false;
                }
            }
                dict[s[i]] = t[i];
                s[i] = t[i];
            }
        }
        if(s == t){
            return true;
        }else {
            return false;
        }

    }
};

yinda_peng

有趣的同构

Judie

yinda_peng 发表于 2023-5-23 01:31
有趣的同构

谢谢！你也刷leetcode嘛！

yinda_peng

Judie 发表于 2023-5-23 14:32
谢谢！你也刷leetcode嘛！

是的，但只是偶尔刷，毕竟我需要花更多的时间在数学上，目前能够独立完成的水平仅限于一部分简单题，因为有些简单题的知识点没有接触过。主要使用C语言和Python

Judie

yinda_peng 发表于 2023-5-23 01:36
是的，但只是偶尔刷，毕竟我需要花更多的时间在数学上，目前能够独立完成的水平仅限于一部分简单题，因为 ...

了解！我打算从今天开始多刷刷

yinda_peng

Judie 发表于 2023-5-23 14:38
了解！我打算从今天开始多刷刷

加油！祝早日offer

Judie

yinda_peng 发表于 2023-5-23 01:39
加油！祝早日offer

谢谢！其实是为了学习算法 准备考试