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;
    }
};
目录
相关文章
|
24天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
31 1
|
1月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
24 9
|
1月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
17 0
|
1月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
28 0
|
1月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
1月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
20 0
|
1月前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
14 0
|
6月前
|
Shell Android开发
Android系统 adb shell push/pull 禁止特定文件
Android系统 adb shell push/pull 禁止特定文件
544 1
|
6月前
|
Android开发 Python
Python封装ADB获取Android设备wifi地址的方法
Python封装ADB获取Android设备wifi地址的方法
150 0
|
3月前
|
Shell Linux 开发工具
"开发者的救星:揭秘如何用adb神器征服Android设备,开启高效调试之旅!"
【8月更文挑战第20天】Android Debug Bridge (adb) 是 Android 开发者必备工具,用于实现计算机与 Android 设备间通讯,执行调试及命令操作。adb 提供了丰富的命令行接口,覆盖从基础设备管理到复杂系统操作的需求。本文详细介绍 adb 的安装配置流程,并列举实用命令示例,包括设备连接管理、应用安装调试、文件系统访问等基础功能,以及端口转发、日志查看等高级技巧。此外,还提供了常见问题的故障排除指南,帮助开发者快速解决问题。掌握 adb 将极大提升 Android 开发效率,助力项目顺利推进。
87 0