Leetcode/205.IsomorphicString.h at master · bluepp/Leetcode · GitHub

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
  2015-05-19
  bluepp
  May the force be with me!

  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.
https://leetcode.com/problems/isomorphic-strings/
*/

/* 2016-09-22, update, one map */

    bool isIsomorphic(string s, string t) {

        if (s.length() != t.length())
        {
            return false;
        }

        unordered_map<char, char> map;

        for (int i = 0; i < s.length(); i++)
        {
            if (map.count(s[i]))
            {
                if (map[s[i]] != t[i])
                {
                    return false;
                }
            }
            else
            {
                for (auto it : map)
                {
                    if (it.second == t[i])
                    {
                        return false;
                    }
                }

                map[s[i]] = t[i];
            }
        }

        return true;

    }


/* 2016-07-01, a simple one */
    bool isIsomorphic(string s, string t) {

        int n = s.length();
        vector<int> m1(256, 0), m2(256, 0);

        for (int i = 0; i < n; i++)
        {
            if (m1[s[i]] != m2[t[i]])
            {
                return false;
            }

            m1[s[i]] = i+1;
            m2[t[i]] = i+1;
        }

        return true;
    }

     bool isIsomorphic(string s, string t) {
        int m = s.size(), n = t.size();
        if (m != n) return false;

        unordered_map<char, char> map_s, map_t;

        for (int i = 0; i < m; i++)
        {
            if (!map_s.count(s[i])) map_s[s[i]] = t[i];
            else
            {
                if (map_s[s[i]] != t[i]) return false;
            }

            if (!map_t.count(t[i])) map_t[t[i]] = s[i];
            else
            {
                if (map_t[t[i]] != s[i]) return false;
            }
        }

        return true;

    }