leetcode 205. Isomorphic Strings 同构字符串判断 + HashMap

古城微笑少年丶 2022-06-08 09:13 168阅读 0赞

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.

这道题考察的是同构字符串的判断，使用HashMap统一编码即可。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    /*
     * 我这里借助map来完成统一的映射，
     * 只需要遍历一次即可
     * */
    public class Solution
    {
        public boolean isIsomorphic(String s, String t)
        {
            if(s==null || t==null)
                return false;
            if(s.length()!=t.length())
                return false;
    
            Map<Character, Integer> map1=new HashMap<Character, Integer>();
            Map<Character, Integer> map2=new HashMap<Character, Integer>();
            int counta=0,countb=0;
            StringBuilder a=new StringBuilder();
            StringBuilder b=new StringBuilder();
    
            for(int i=0;i<s.length();i++)
            {
                if(map1.containsKey(s.charAt(i)))
                    a.append(map1.get(s.charAt(i)));
                else
                {
                    map1.put(s.charAt(i), counta);
                    a.append(counta);
                    counta++;
                }
    
                if(map2.containsKey(t.charAt(i)))
                    b.append(map2.get(t.charAt(i)));
                else
                {
                    map2.put(t.charAt(i), countb);
                    b.append(countb);
                    countb++;
                }
    
                //而这需要同步，所以这里加了一个小小的判断
                if(counta!=countb)
                    return false;
            }
            if(a.toString().equals(b.toString()))
                return true;
            else
                return false;
        }
    }

下面是C++的做法，就是做统一编码，做一次遍历即可解决问题

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <algorithm>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool isIsomorphic(string s, string t) 
        {
            if (s.length() != t.length())
                return false;
            map<char,int> mp1, mp2;
            int key1 = 0, key2 = 0;
            string res1 = "", res2 = "";
            for (int i = 0; i < s.length(); i++)
            {
                if (mp1.find(s[i]) != mp1.end() )
                    res1 += to_string(mp1[s[i]]);
                else
                {
                    mp1[s[i]] = key1;
                    res1 += to_string(key1++);
                }
    
                if (mp2.find(t[i]) != mp2.end())
                    res2 += to_string(mp2[t[i]]);
                else
                {
                    mp2[t[i]] = key2;
                    res2 += to_string(key2++);
                }
                if (key1 != key2)
                    return false;
            }
            return res1 == res2;
        }
    };