[LeetCode] Isomorphic Strings - 字符串操作:数组计数字符个数问题

举报
eastmount 发表于 2021/07/31 19:13:46 2021/07/31
【摘要】 这是一道关于字符串操作数组计数字符个数的LeetCode题目,希望对您有所帮助。

题目概述:

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.

解题方法:
        该题意是判断两个字符串s和t是否是同构的。(注意字符不仅是字母)
        最简单的方法是通过计算每个字符出现的个数并且相应位置字母对应,但是两层循环肯定TLE。所以需要通过O(n)时间比较,采用的方法是:
        eg: "aba" <> "baa"  return false
        关键代码:nums[s[i]]=t[i]  numt[t[i]]=s[i] 再比较是否相同 
        nums['a']='b' numt['b']='a'  (第一次出现)
        nums['b']='a' numt['a']='b'  (第一次出现)
        nums['a']='b' <> t[2]='a'     (第二次出现)  return false
        该方法技巧性比较强,当然如果你使用C++的映射就非常容易实现了。

我的代码:

bool isIsomorphic(char* s, char* t) {
    int ls,lt;     //字符串长度
    int i,j;
    int nums[256]={0};
    int numt[256]={0};
    
    ls = strlen(s);
    lt = strlen(t);
    if(ls!=lt) return false;
    for(i=0; i<ls; i++) {
        //初值为0
        if(nums[s[i]]==0) {
            if(numt[t[i]]==0) {
                nums[s[i]] = t[i];
                numt[t[i]] = s[i];
            }
            else {
                return false;
            }
        }
        else {
            if(nums[s[i]]!=t[i]) {
                return false;
            }
        }
    }
    return true;
}

C++推荐代码:

        参考:http://www.cnblogs.com/easonliu/p/4465650.html
        题目很简单,也很容易想到方法,就是记录遍历s的每一个字母,并且记录s[i]到t[i]的映射,当发现与已有的映射不同时,说明无法同构,直接return false。但是这样只能保证从s到t的映射,不能保证从t到s的映射,所以交换s与t的位置再重来一遍上述的遍历就OK了。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) return false;
        map<char, char> mp;
        for (int i = 0; i < s.length(); ++i) {
            if (mp.find(s[i]) == mp.end()) mp[s[i]] = t[i];
            else if (mp[s[i]] != t[i]) return false;
        }
        mp.clear();
        for (int i = 0; i < s.length(); ++i) {
            if (mp.find(t[i]) == mp.end()) mp[t[i]] = s[i];
            else if (mp[t[i]] != s[i]) return false;
        }
        return true;
    }
};


2015年的文章,希望您喜欢。
原文地址:https://blog.csdn.net/Eastmount/article/details/48614121

(By:Eastmount 2021-7-31 夜于武汉)

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。