leetcode-205-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,

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

分析

判断两个字符串是否是同构的。给定两个字符串，如果将一个字符串中某个字符换成另一个字符(可以多次)，可以得到另一个字符串，那么返回true，否则返回false。所以字符与字符是一一对应的，用map解决即可。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int sizeof_s = s.size();
        int sizeof_t = t.size();
        
        if(sizeof_s != sizeof_t) {
            return false;
        }
        unordered_map<char, char> char_map_s;
        unordered_map<char, char> char_map_t;
        for(int i = 0; i < sizeof_s; i++) {
            char now_s = s[i];
            char now_t = t[i];
            if(char_map_s.find(now_s) != char_map_s.end() && char_map_s[now_s] != now_t) {
                return false;
            }
            if(char_map_t.find(now_t) != char_map_t.end() && char_map_t[now_t] != now_s) {
                return false;
            }
            char_map_s[now_s] = now_t;
            char_map_t[now_t] = now_s;
        }
        return true;
    }
};

解决方案2（Java）

这里是一种稍稍不同的思路，用一个set存放已经被映射的字符，如果有两个不同的字符映射到同一个字符，返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> map_char_char = new HashMap<Character, Character>();
        Set<Character> set_char = new HashSet<Character>();
        
        for(int i = 0; i < s.length(); i++) {
            char char_s = s.charAt(i);
            char char_t = t.charAt(i);
            if(!map_char_char.containsKey(char_s) && !set_char.contains(char_t)) {
                map_char_char.put(char_s, char_t);
                set_char.add(char_t);
            }else if(map_char_char.containsKey(char_s) && map_char_char.get(char_s) == char_t) {
                continue;
            }else {
                return false;
            }
        }
        return true;
    }
}

解决方案3(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        map_dict = {}
        mapped = set()
        
        if len(s) != len(t):
            return false
        
        for i in range(len(s)):
            if s[i] not in map_dict and t[i] not in mapped:
                map_dict[s[i]] = t[i]
                mapped.add(t[i])
            elif s[i] in map_dict and map_dict[s[i]] == t[i]:
                pass
            else:
                return False
        return True

相关问题

(E) Word Pattern

题目来源