LeetCode 205 Isomorphic Strings(同构的字符串)(string、vector、map)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611168 翻译给定两个字符串s和t,决定它们是否是同构的。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611168

翻译

给定两个字符串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<int> getVecOrder(string str) {
    map<char, int> strM;
    int index = 0;
    vector<int> strVec;
    for (int i = 0; i < str.size(); ++i) {
        auto iter = strM.find(str[i]);
        if (iter == strM.end()) {
            strM.insert(pair<char, int>(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<int> 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<Character, Integer> 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<int> getVecOrder(string str) {
        int len = str.size();
        map<char, int> strM;
        int index = 0;
        vector<int> strVec;
        for (int i = 0; i < len; ++i) {
            auto iter = strM.find(str[i]);
            if (iter == strM.end()) {
                strM.insert(pair<char, int>(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<int> 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;
    }
};
目录
相关文章
|
3月前
|
安全 Java API
【Java字符串操作秘籍】StringBuffer与StringBuilder的终极对决!
【8月更文挑战第25天】在Java中处理字符串时,经常需要修改字符串,但由于`String`对象的不可变性,频繁修改会导致内存浪费和性能下降。为此,Java提供了`StringBuffer`和`StringBuilder`两个类来操作可变字符串序列。`StringBuffer`是线程安全的,适用于多线程环境,但性能略低;`StringBuilder`非线程安全,但在单线程环境中性能更优。两者基本用法相似,通过`append`等方法构建和修改字符串。
59 1
|
19天前
|
NoSQL Redis
Redis 字符串(String)
10月更文挑战第16天
31 4
|
1月前
|
canal 安全 索引
(StringBuffer和StringBuilder)以及回文串,字符串经典习题
(StringBuffer和StringBuilder)以及回文串,字符串经典习题
33 5
|
1月前
|
存储 JavaScript 前端开发
JavaScript 字符串(String) 对象
JavaScript 字符串(String) 对象
40 3
|
3月前
|
NoSQL 安全 Java
Redis6入门到实战------ 三、常用五大数据类型(字符串 String)
这篇文章深入探讨了Redis中的String数据类型,包括键操作的命令、String类型的命令使用,以及String在Redis中的内部数据结构实现。
Redis6入门到实战------ 三、常用五大数据类型(字符串 String)
|
2月前
|
存储 C++
C++(五)String 字符串类
本文档详细介绍了C++中的`string`类,包括定义、初始化、字符串比较及数值与字符串之间的转换方法。`string`类简化了字符串处理,提供了丰富的功能如字符串查找、比较、拼接和替换等。文档通过示例代码展示了如何使用这些功能,并介绍了如何将数值转换为字符串以及反之亦然的方法。此外,还展示了如何使用`string`数组存储和遍历多个字符串。
|
3月前
|
C# 开发者 UED
WPF开发者必备秘籍:深度解析文件对话框使用技巧,打开与保存文件原来如此简单!
【8月更文挑战第31天】在WPF应用开发中,文件操作是常见需求。本文详细介绍了如何利用`Microsoft.Win32`命名空间下的`OpenFileDialog`和`SaveFileDialog`类来正确实现文件打开与保存功能。通过示例代码展示了如何设置文件过滤器、初始目录等属性,并使用对话框进行文件读写操作。正确使用文件对话框能显著提升用户体验,使应用更友好易用。
70 0
|
3月前
|
API C# 开发者
WPF图形绘制大师指南:GDI+与Direct2D完美融合,带你玩转高性能图形处理秘籍!
【8月更文挑战第31天】GDI+与Direct2D的结合为WPF图形绘制提供了强大的工具集。通过合理地使用这两种技术,开发者可以创造出性能优异且视觉效果丰富的WPF应用程序。在实际应用中,开发者应根据项目需求和技术背景,权衡利弊,选择最合适的技术方案。
130 0
|
3月前
|
存储 JSON NoSQL
揭秘Redis字符串String的隐藏技能!从基础到进阶,让你的数据存储操作秒变高大上!
【8月更文挑战第24天】Redis中的字符串类型作为其基石,不仅能够存储从简单文本到复杂格式如JSON的各种数据,还能通过多样化的命令实现包括但不限于自增自减、设置过期时间等高级功能,极大提升了其实用性和灵活性。例如,使用`SET`命令可添加或更新键值对,`GET`获取值,`DEL`删除键;同时,`INCR`和`DECR`支持对整数值的原子性增减操作,非常适合实现计数器等功能;通过`EXPIRE`命令设置过期时间,则适用于需要限时存储的应用场景。尽管名为“字符串”,但实际上还可存储图片、音频文件的Base64编码等形式的数据,为开发者提供了强大而灵活的工具。
47 0
|
3月前
|
存储 Java