leetcode 205 Isomorphic String
z
 2017-12-26 11:39:32  

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.

Note:
You may assume both s and t have the same length.

  • 首先想到的是利用HashMap，保存分别保存当前的字符和对应的下标。
  • 如果s[i]和t[i]都已经存在与各自的hashmap中，判断其value是否一致，及第一次出现的下标是否一致
  • 还要判断，当si、ti都不存在与各自的hashmap中时，将其保存到各自的hashMap中
  • 否在，si存在而ti不存在，或者si不存在ti存在，返回false
  • 返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Integer> m1 = new HashMap<Character, Integer>();
        HashMap<Character, Integer> m2 = new HashMap<Character, Integer>();
        for(int i=0;i<s.length();i++){
            if(m1.containsKey(s.charAt(i)) && m2.containsKey(t.charAt(i))){
                if(m1.get(s.charAt(i)) != m2.get(t.charAt(i))){
                    return false;
                }
            }
            else if(!m1.containsKey(s.charAt(i)) && !m2.containsKey(t.charAt(i)))
            {
                m1.put(s.charAt(i),i);
                m2.put(t.charAt(i),i);
            }
            else{
                return false;
            }
        }
        return true;
    }
}

这里用到了两个hashmap，但是可以优化为只用一个hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> m = new HashMap<Character, Character>();
        for(int i=0; i<s.length(); i++){
            if(m.containsKey(s.charAt(i))){
                if(m.get(s.charAt(i))!= t.charAt(i)){
                    return false;
                }
            }
            else if (m.containsValue(t.charAt(i))){
                return false;
            }
            m.put(s.charAt(i), t.charAt(i));
        }
        return true;
    }
}

但是这个的时间效率更低

还有一种设置两个256长度的int[]数组。

初始化为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256];
        int[] m2 = new int[256];
        for(int i=0;i<s.length(); i++){
            if(m1[s.charAt(i)] != m2[t.charAt(i)]){
                return false;
            }
            else{
                m1[s.charAt(i)] = i+1;// 注意这里是i+1
                m2[t.charAt(i)] = i+1;    
            }
            
        }
        return true;
    }
}

之所以是i+1，是存在这种情况

如果是i：

i=0时，if不成立，

”a b“ m1[‘a’] = 0

“a a” m2[‘a’] = 0

i=1时， if不成立，

​ m1[‘a’] = 1

​ m2[‘a’] = 1

return true;