Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

同构字符串

Posted on In , ,
Symbols count in article: 1.8k Reading time ≈ 2 mins.

来自Leetcode第205题同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

1
2
输入: s = "egg", t = "add"
输出: true

Hash

维护一个HashMap，里面存放2个字符串相对的映射方式，要注意Map里的元素应当是唯一的，如果出现重复，可以直接返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isIsomorphic(String s, String t) {
    if(s.equals("") || s == null)
        return true;
    char tmp_t,tmp_s;
    HashMap<Character,Character> map = new HashMap<>();
    for(int i = 0 ;i < s.length() ; i++){
        tmp_s = s.charAt(i);
        tmp_t = t.charAt(i);
        if(!map.containsKey(tmp_s)){
            if(!map.containsValue(tmp_t)) 
                map.put(tmp_s,tmp_t);
            else
                return false;
        }else
        {
            if(tmp_t != map.get(tmp_s))
                return false;
        }
    }
    return true;
}

字母映射成数字

最开始写的时候是考虑过将字符串add映射成122这种形式，最后比较生成的2个字符串是否一致即可，于是我选择了维护2个HashMap，但是这导致了超时。

原代码如下

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 boolean isIsomorphic(String s, String t) {
    if(s.equals("") || s == null)
        return true;
    String s1 = "",s2 = "";
    HashMap<Character,Integer> map1 = new HashMap<>();
    HashMap<Character,Integer> map2 = new HashMap<>();
    for(int i = 0 ;i < s.length() ; i++){
        if(!map1.containsKey(s.charAt(i))){
            map1.put(s.charAt(i),i);
            s1 += i;
        }
        else
            s1 += map1.get(s.charAt(i));
        if(!map2.containsKey(t.charAt(i))){
            map2.put(t.charAt(i),i);
            s2 += i;
        }
        else
            s2 += map2.get(t.charAt(i));
        if(!s1.equals(s2))
            return false;
    }
    return true;
}

在参考了windliang的解答后发现可以不用HashMap，可以直接用2个数组处理，但是本质思想是差不多的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isIsomorphic(String s, String t) {
    if(s.equals("") || s == null)
        return true;
    char tmp_t,tmp_s;
    int len = s.length();
    int[] map1 = new int[128];
    int[] map2 = new int[128];
    for(int i = 0 ; i < len; i ++){
        tmp_s = s.charAt(i);
        tmp_t = t.charAt(i);
        if(map1[tmp_s] != map2[tmp_t])
            return false;
        else{
            if(map1[tmp_s] == 0){
                map1[tmp_s] = i + 1;
                map2[tmp_t] = i + 1;
            }
        }
    }
    return true;
}