LeetCode 205 Isomorphic Strings（同构的字符串）（string、vector、map）（*）-白红宇

LeetCode 205 Isomorphic Strings（同构的字符串）（string、vector、map）（*）

阅读量：6956 次

发布时间：2019-06-27

本文共 3549 字，大约阅读时间需要 11 分钟。

翻译

给定两个字符串s和t，决定它们是否是同构的。假设s中的元素被替换能够得到t，那么称这两个字符串是同构的。在用一个字符串的元素替换还有一个字符串的元素的过程中。所有字符的顺序必须保留。

没有两个字符能够被映射到同样的字符，但字符能够映射到该字符本身。比如，给定“egg”，“add”，返回真。给定“foo”。“bar”，返回假。给定“paper”，“title”，返回真。

批注：你能够假设s和t有同样的长度。

原文

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.

分析

翻译完这题目就非常自然的想到一个方法，我希望将字符串所有输出成数字序列：

For example,Given "paper", return "01023".Given "foo", return "011".Given "isomorphic", return "0123245607".

于是就将这个功能给实现了：

vector
      
        getVecOrder(string str) {    map
       
         strM;    int index = 0;    vector
        
          strVec;    for (int i = 0; i < str.size(); ++i) {        auto iter = strM.find(str[i]);        if (iter == strM.end()) {            strM.insert(pair
         
          (str[i], index));            strVec.push_back(index);            index += 1;        }        else {            strVec.push_back(strM[str[i]]);        }    }    return strVec;}

这里用map来保存每一个字符和索引的键值对，索引用index来表示。索引从0開始。

最后的数字序列用vector来保存。

循环遍历整个字符串，每次在map中寻找一个字符，假设没有找到，则将其和相应的index加入进去，假设已经存在，就将该字符的索引从map中获取出来并加入到vector中。

有了这个模块函数，解起题来就轻而易举咯：

bool isIsomorphic(string s, string t) {    vector
      
        v_s = getVecOrder(s), v_t = getVecOrder(t);    for (int i = 0; i < v_s.size(); ++i) {        if (v_s[i] != v_t[i]) return false;    }                                                      return true;}

由于字符串的长度题目说了是等长的，所以vector的长度肯定也是相等的了。

updated at 2016/09/05

同理，也能够改成例如以下所看到的的 Java 代码~

private ArrayList getArrayOrder(String str) {        HashMap
      
        strM = new HashMap<>();        int index = 0;        ArrayList order = new ArrayList(str.length());        for (int i = 0; i < str.length(); i++) {            char c = str.charAt(i);            if (strM.containsKey(c)) {                order.add(strM.get(c));            } else {                strM.put(c, index);                order.add(index);                index += 1;            }        }        return order;    }    public boolean isIsomorphic(String s, String t) {        if (s.length() != t.length())            return false;        ArrayList s0 = getArrayOrder(s), t0 = getArrayOrder(t);        for (int i = 0; i < s0.size(); i++)            if (s0.get(i) != t0.get(i))                return false;        return true;    }

代码

class Solution {public:    vector
      
        getVecOrder(string str) {        int len = str.size();        map
       
         strM;        int index = 0;        vector
        
          strVec;        for (int i = 0; i < len; ++i) {            auto iter = strM.find(str[i]);            if (iter == strM.end()) {                strM.insert(pair
         
          (str[i], index));                strVec.push_back(index);                index += 1;            }            else {                strVec.push_back(strM[str[i]]);            }        }        return strVec;    }    bool isIsomorphic(string s, string t) {        vector
          
            v_s = getVecOrder(s), v_t = getVecOrder(t);        for (int i = 0; i < v_s.size(); ++i) {            if (v_s[i] != v_t[i]) return false;        }        return true;    }};

转载地址：http://nsmil.baihongyu.com/

你可能感兴趣的文章